Sorting & Searching

Question 1 (10)

(a) (3) The comparison-sort model: algorithm accesses input only through comparisons $a_i \lessgtr a_j$; it may not inspect key values otherwise. Each comparison has two outcomes → binary branching. A run is a root-to-leaf path; each leaf must correspond to a distinct permutation that reorders the input into sorted order. (1 model, 1 binary branching, 1 leaves = permutations)

(b) (5)

• There are $n!$ possible input orderings, all needing distinct sorted outputs, so the tree must have $\ge n!$ leaves. (1)
• A binary tree of height $h$ has at most $2^h$ leaves, so $2^h \ge n! \Rightarrow h \ge \log_2(n!)$. (1)
• Worst-case comparisons $=$ height $h$. (1)
• Stirling: $\log_2(n!) = \sum_{i=1}^n \log_2 i \ge \int_1^n \log_2 x\,dx = \Theta(n\log n)$; more precisely $n! \ge (n/e)^n$ so $\log_2(n!) \ge n\log_2 n - n\log_2 e = \Omega(n\log n)$. (2)

(c) (2) False: the $\Omega(n\log n)$ lower bound holds for the worst case of any comparison sort, so no comparison sort can be $O(n)$ on every input. (non-comparison sorts like counting sort escape by not being comparison-based.)

Question 2 (12)

(a) (5)

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    for j = lo to hi-1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i], A[j]
    swap A[i+1], A[hi]
    return i + 1

Returns final pivot index $p$. Invariant: at start of each iteration, A[lo..i] <= pivot and A[i+1..j-1] > pivot. (3 code, 1 return, 1 invariant)

(b) (3) An already-sorted (ascending) array with last-element pivot: pivot is always the max, partition splits into sizes $n-1$ and $0$. Recurrence $T(n)=T(n-1)+\Theta(n) = \Theta(n^2)$. (1 input, 2 justification)

(c) (4) Randomly choosing the pivot makes the partition split independent of input order; every element is equally likely to be pivot. Using indicator $X_{ij}=[z_i \text{ compared with } z_j]$, $z_i,z_j$ are compared iff one is the first pivot chosen from the range $z_i..z_j$, giving $\Pr = \frac{2}{j-i+1}$. Then $E[\text{comparisons}] = \sum_{i<j}\frac{2}{j-i+1} = O(n\ln n)$ (harmonic sum). Expectation is over the random pivots, so it holds for every input. (1 pivot indep, 1 indicator setup, 1 prob 2/(j-i+1), 1 harmonic sum→O(n log n))

Question 3 (10)

(a) (3) $T(n)=2T(n/2)+\Theta(n)$. Master Theorem: $a=2,b=2,f(n)=\Theta(n)$, $n^{\log_b a}=n^1$; since $f(n)=\Theta(n^{\log_b a})$ this is Case 2 → $T(n)=\Theta(n\log n)$.

(b) (4) Loop invariant during merge: the output built so far is a sorted permutation of the consumed prefixes, and among consumed elements, equal keys retain input relative order. On a tie (L[i] == R[j]), we take from left first. Since left subarray held earlier-input elements, taking left preserves original order for equal keys. Maintenance: each step either extends invariant by a strictly correct or tie-broken-left element. Termination gives full stable merge. (1 invariant, 1 tie-break rule, 2 argument)

(c) (3) Split $[5_a,3]$ and $[5_b,1,4]$. Sorted: $[3,5_a]$ and $[1,4,5_b]$. Merge → $[1,3,4,5_a,5_b]$. The order $5_a$ before $5_b$ is preserved → stable confirmed. (2 trace, 1 conclusion)

Question 4 (12)

(a) (5) Median-of-medians select(A,k):

1. Divide $n$ elements into $\lceil n/5\rceil$ groups of 5.
2. Sort each group, take its median → collect medians.
3. Recursively select the median-of-medians $M$ of those medians.
4. Partition $A$ around $M$; let $M$ have rank $r$.
5. If $k=r$ return $M$; if $k<r$ recurse left; else recurse right for $k-r$. (1 each step)

(b) (4) There are $\lceil n/5\rceil$ group medians. $M$ is $\ge$ half of them, i.e. $\ge \tfrac{1}{2}\lceil n/5\rceil$ medians. Each such median has 2 elements in its group $\le$ it (plus itself), so at least $3\left(\tfrac{1}{2}\lceil n/5\rceil - 2\right) \ge \tfrac{3n}{10} - 6$ elements are $\le M$. By symmetry the same count is $\ge M$. Hence each recursive partition discards $\ge 3n/10$ elements, leaving $\le 7n/10$. (2 median count, 2 the 3n/10 bound)

(c) (3) $T(n)\le T(\lceil n/5\rceil)+T(7n/10)+O(n)$. Since $\tfrac15+\tfrac{7}{10}=\tfrac{9}{10}<1$, the subproblem sizes form a geometric-decaying sum; guess $T(n)\le cn$, then $c\,n/5 + 7cn/10 + an = \tfrac{9c}{10}n + an \le cn$ holds for $c\ge 10a$. Hence $T(n)=O(n)$. (1 recurrence, 2 argument)

Question 5 (8)

(a) (5)

countingSort(A, k):
    C = array[0..k] of 0
    for x in A: C[x] += 1
    for i = 1 to k: C[i] += C[i-1]        # prefix sums
    B = array[0..n-1]
    for j = n-1 downto 0:                  # right-to-left
        x = A[j]
        C[x] -= 1
        B[C[x]] = x
    return B

C[x] after prefix sum = number of elements $\le x$ = last output slot for key $x$. Iterating right-to-left and decrementing places later-input equal keys into later slots, preserving input order → stable. (3 code, 2 stability explanation)

(b) (3) Plain counting sort needs a count array of size $k+1 = 10^9+1$ → ~4 GB memory, far exceeding $n$; time/space $O(n+k)$ dominated by $k \gg n$. LSD radix with base $b=10^3$: each digit range is $[0,999]$ (small $k=1000$), and $d = \lceil \log_{1000}(10^9) \rceil = 3$ passes of stable counting sort → $O(d(n+b)) = O(3(10^6+10^3))$. d = 3. (2 why bad, 1 d=3)

Question 6 (8)

(a) (5)

search(A, target):
    lo, hi = 0, len(A)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if A[mid] == target: return mid
        if A[lo] <= A[mid]:                 # left half sorted
            if A[lo] <= target < A[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                               # right half sorted
            if A[mid] < target <= A[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

(4 code correctness, 1 correct −1 return)

(b) (3) Invariant: for any window [lo,hi], at least one of the two halves split at mid is fully sorted (rotation point lies in the other half). Determine the sorted half by comparing A[lo] vs A[mid]. If target lies within that sorted half's value range, recurse there; otherwise recurse into the other half. This halves the search each step → $O(\log n)$. (1 invariant, 1 which-half test, 1 halving)

[
  {"claim":"log2(n!) >= n log2 n - n log2 e (Stirling lower bound direction) at n=8", "code":"import math\nn=8\nlhs=math.log2(math.factorial(n))\nrhs=n*math.log2(n)-n*math.log2(math.e)\nresult = lhs >= rhs"},
  {"claim":"Randomized quicksort expected comparisons sum 2/(j-i+1) equals 2*(n+1)*H_n - 4n form; check n=4 numeric", "code":"from sympy import Rational\nn=4\ntotal=0\nfor i in range(1,n+1):\n    for j in range(i+1,n+1):\n        total+=Rational(2,j-i+1)\nresult = total == Rational(2*(sum(Rational(1,t) for t in range(1,n+1)))*(n+1)-4*n)"},
  {"claim":"Radix passes d for range 1e9 base 1000 is 3", "code":"import math\nd=math.ceil(math.log(10**9, 1000))\nresult = d == 3"},
  {"claim":"Median-of-medians leaves at most 7n/10 (approx) so 1/5+7/10<1", "code":"from sympy import Rational\nresult = Rational(1,5)+Rational(7,10) < 1"}
]