Question 1: Describe in your own words how a bubble sort algorithm works to sort a list of numbers.

Answer: Bubble sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process repeats until no swaps are needed, resulting in a sorted list.

Question 2: Given the list of numbers: 8, 3, 5, 1, 4, show the list after the first pass of the bubble sort algorithm.

Answer: After the first pass, the list would be: 3, 5, 1, 4, 8.

Question 3: Explain the difference between a merge sort and a quick sort algorithm.

Answer: Merge sort divides the list into smaller parts, sorts them recursively, and then merges the sorted parts. Quick sort selects a pivot, partitions the list into elements less than and greater than the pivot, and sorts the partitions recursively.

Question 4: Describe a scenario where insertion sort might be preferable over other sorting algorithms.

Answer: Insertion sort is preferable when sorting small or nearly sorted datasets because it is simple and efficient in those cases.

Question 5: Complete the truth table for the AND gate with inputs A and B and output C:

Answer: Inputs: A, B; Output: C | A | B | C | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

Question 6: Complete the truth table for the OR gate with inputs A and B and output C:

Answer: Inputs: A, B; Output: C | A | B | C | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

Question 7: Draw a logic circuit using AND, OR, and NOT gates that represents the logical expression: (A AND B) OR (NOT C).

Answer: A correct sketch would include: an AND gate with inputs A and B, a NOT gate with input C, and an OR gate combining the outputs of the AND gate and the NOT gate.

Question 8: Sketch a flowchart that describes the process of sorting a list of numbers using bubble sort.

Answer: A correct sketch would include: start symbol, a loop structure comparing and swapping adjacent elements, a condition to check if any swaps occurred, and an end symbol.

Question 9: Explain why merge sort has a better worst-case time complexity than bubble sort.

Answer: Merge sort has a time complexity of O(n log n) because it divides the list into halves and merges sorted parts efficiently. Bubble sort has a worst-case time of O(n^2) because it repeatedly compares and swaps adjacent elements, which takes longer as the list grows.

Question 10: Describe how you could modify a bubble sort algorithm to make it more efficient when the list is already nearly sorted.

Answer: You can add a flag to check if any swaps occurred during a pass. If no swaps happen, the list is already sorted, and the algorithm can stop early.