Mid-semester.
Questions, answered.

Write an in-place Merge Sort algorithm. Discuss the time complexity of the algorithm.

Algorithm: IN-PLACE-MERGE-SORT(A, left, right)

1. If left ≥ right, return.
2. Set mid ← ⌊(left + right) / 2⌋.
3. Call IN-PLACE-MERGE-SORT(A, left, mid).
4. Call IN-PLACE-MERGE-SORT(A, mid + 1, right).
5. Call GAP-MERGE(A, left, right).

Initially, call IN-PLACE-MERGE-SORT(A, 0, n − 1). In step 5, both adjacent halves are already sorted.

Algorithm: GAP-MERGE(A, left, right)

1. Set length ← right − left + 1.
2. If length ≤ 1, return.
3. Set gap ← ⌈length / 2⌉.
4. While gap > 0, repeat:
   a. Set i ← left and j ← left + gap.
   b. While j ≤ right, repeat:
      i.   If A[i] > A[j], swap A[i] and A[j].
      ii.  Set i ← i + 1 and j ← j + 1.
   c. If gap = 1, set gap ← 0.
      Otherwise, set gap ← ⌈gap / 2⌉.
5. Return.

For nine elements, the gaps are 5, 3, 2 and 1.

Time complexity

A merge of m elements has O(log m) gap passes, each taking O(m) time. Hence one gap-merge takes O(m log m). Using this merge at every level of Merge Sort gives:

Alternative: swap and re-sort

1. For two sorted arrays A and B of sizes n and m, set i ← n − 1 and j ← 0.
2. While i ≥ 0 and j < m, compare A[i] and B[j]. If A[i] > B[j], swap them, decrease i by 1 and increase j by 1. Otherwise, stop the scan.
3. Sort A and B separately in place. Their concatenation is now sorted.

Time complexity: O(min(n, m)) + O(n log n) + O(m log m).

Why do Merge Sort and Quick Sort generally use two-way partitioning instead of more than two parts? Does a smaller recursion depth, such as log₃ n instead of log₂ n, necessarily reduce the overall time complexity?

No. Changing the depth from log₂ n to log₃ n gives only a constant-factor improvement, since

Therefore, n log₂ n and n log₃ n are both Θ(n log n). Dividing into three parts does not improve the asymptotic time complexity. Two-way splitting is simpler; fewer recursion levels alone do not change the order of growth.

Suppose you have 90 GB of unsorted data stored on a hard disk, while the available RAM is only 10 GB. Write an algorithm to efficiently sort the entire dataset using a min-heap data structure.

Algorithm: EXTERNAL-SORT

1. Divide the 90 GB dataset into chunks that fit in the 10 GB RAM. Ignoring working-space overhead, this gives nine chunks of 10 GB each; leave room for working memory in an implementation.
2. Read one chunk into RAM, sort it, and write the sorted chunk back to disk as a separate file.
3. Repeat step 2 for every chunk.
4. Read about 90 MB of complete records from each sorted file into a separate input buffer in RAM. Also reserve an output buffer of about 90 MB.
5. Create a min-heap.
6. Extract the minimum element from the heap and append it to the output buffer.
7. Advance to the next element in the input buffer that supplied the extracted element. If that buffer is exhausted, refill it with the next block of about 90 MB from the same file. Insert the next element into the min-heap. If both the buffer and its file are exhausted, do not insert a replacement.
8. When the output buffer reaches about 90 MB, append its contents to the output file on disk and empty the buffer.
9. Repeat steps 6–8 until the heap becomes empty.
10. Write any remaining elements in the output buffer to disk. The output file now contains all 90 GB in sorted order.

Each input buffer contributes only its smallest unprocessed element to the heap. The remaining elements stay in the buffer. This keeps the output globally sorted while disk reads and writes take place in blocks.

For nine sorted files, the input buffers use about 9 × 90 MB = 810 MB. Including the 90 MB output buffer gives about 900 MB, plus the small heap and bookkeeping, which fits within 10 GB RAM.

Write an algorithm/pseudocode to reverse a singly linked list using recursion.

Algorithm: REVERSE(prev, cur)

head is the list’s shared head pointer.

1. If cur ≠ NULL, go to step 2; otherwise go to step 4.
2. Call REVERSE(cur, cur.next).
3. Set cur.next ← prev, then return.
4. Set head ← prev, then return.

Start by calling REVERSE(NULL, head). The procedure changes the head pointer and the existing links; it does not return a new head as a value.

Alternative algorithm: Reverse(head)

1. If head = NULL or head.next = NULL:
   Return head.

2. Set newHead ← Reverse(head.next).

3. Set head.next.next ← head.

4. Set head.next ← NULL.

5. Return newHead.

Call head ← Reverse(head) to update the list’s head.

For 1 → 2 → 3 → NULL, show the complete contents of the recursion stack at each stage, including variable state and the next line to be executed.

Write an optimized recursive algorithm for computing aⁿ, where n is a natural number. Write the corresponding recurrence relation and state its time complexity.

Using exponentiation by squaring: If n is even, aⁿ = (a^n/2)². If n is odd, aⁿ = a × (a^(n−1)/2)². The half-power is calculated once and reused.

Algorithm: POWER(a, n)

1. If n = 0, return 1.
2. Set half ← POWER(a, ⌊n / 2⌋).
3. If n is even, return half × half.
4. Otherwise, return a × half × half.

Recurrence and complexity

Each recursive call halves n, so the number of calls is logarithmic.

A BST is constructed by inserting n elements one by one into an initially empty tree. Discuss the average-case and worst-case time complexities. What insertion order leads to the worst case?

Average case: For a reasonably balanced insertion order, each insertion takes O(log n) time. Therefore, inserting all n elements takes O(n log n) time.

Worst case: Increasing or decreasing insertion order makes an ordinary BST skewed. The insertion costs grow as 1, 2, 3, …, n, so their sum is O(n²).

For example, the sorted order 3, 5, 7, 10, 12, 15, 18 creates a right-skewed BST. Reversing the order creates a left-skewed BST.

Which tree traversal is most suitable for deleting all nodes of a binary tree, and why? Write the corresponding pseudocode.

Postorder traversal is most suitable. Its order is left subtree, right subtree, then root. Thus, both children are deleted before their parent, so the child pointers remain available until they are no longer needed.

Algorithm: DELETE-TREE(node)

1. If node = NULL, return.
2. Call DELETE-TREE(node.left).
3. Call DELETE-TREE(node.right).
4. Delete node.
5. Return.

Call DELETE-TREE(root) and then set root ← NULL.