Algorithm Paradigms

Question 1 (12)

(a) Sort by finish: A(3), B(4), C(6), D(7). Earliest-finish greedy: pick A (finish 3). Next compatible must have start $\ge 3$: C (start 3) — pick. Next start $\ge 6$: D starts 4 (no). None. Greedy schedule = {A, C}, weight $= 5+5 = 10$. (3) (correct schedule 2, weight 1)

(b) Optimal: {B, D}, weight $= 6+6 = 12$. B(1–4), D(4–7) compatible. Unweighted greedy ignores weights — it optimizes count/earliest finish, so it can pick low-weight jobs. (3) (schedule+weight 2, reason 1)

(c) Sort jobs by finish time. Define $p(i)$ as given. $\text{OPT}(i) = \max\big(\underbrace{w_i + \text{OPT}(p(i))}_{\text{include } i},\ \underbrace{\text{OPT}(i-1)}_{\text{exclude } i}\big),\quad \text{OPT}(0)=0.$ Include: take $w_i$ plus best from jobs finishing before $s_i$. Exclude: best without job $i$. (4) (recurrence 2, two-choice explanation 2)

(d) Sorting $O(n\log n)$ dominates; each $p(i)$ by binary search $O(\log n)$; DP fill $O(n)$. Total $O(n\log n)$. (2)

Question 2 (12)

(a)

• $\text{same}(i)$: posts $i-1,i$ equal ⇒ previous pair $i-2,i-1$ must differ (else 3 same). So $\text{same}(i) = \text{diff}(i-1)$.
• $\text{diff}(i)$: post $i$ differs from $i-1$, and it can be any of the other $k-1$ colours regardless of the earlier pair: $\text{diff}(i) = (k-1)\cdot(\text{same}(i-1) + \text{diff}(i-1))$.
• Base ($i=2$): $\text{same}(2)=k$, $\text{diff}(2)=k(k-1)$.

(6) (same recurrence 2, diff recurrence 2, base 2)

(b) $k=3$:

• $i=2$: same=3, diff=6, total=9.
• $i=3$: same = diff(2)=6; diff = 2·(3+6)=18; total=24.
• $i=4$: same = diff(3)=18; diff = 2·(6+18)=48; total=66.

Answer: 66 ways. (4)

(c) Time $O(n)$, space $O(n)$ (or $O(1)$ by keeping only previous same, diff and rolling them each step). (2)

Question 3 (12)

(a) State: $\text{dp}[S][j]$ = min cost path starting at city 0, visiting exactly the set $S$ of cities, ending at city $j\in S$. Recurrence: $\text{dp}[S][j] = \min_{i \in S\setminus\{j\}} \text{dp}[S\setminus\{j\}][i] + \text{dist}(i,j).$ Base $\text{dp}[\{0\}][0]=0$. Answer $= \min_j \text{dp}[\text{full}][j]+\text{dist}(j,0)$. Time $O(2^n \cdot n^2)$, space $O(2^n \cdot n)$. (5)

(b) (i) lowest set bit: x & (-x). (ii) clear lowest set bit: x & (x-1). (iii) power of two: x != 0 and (x & (x-1)) == 0. (3) (1 each)

(c) XOR all elements: ans = a[0] ^ a[1] ^ ... . Since $x\oplus x=0$ and XOR is associative/commutative, all paired values cancel, leaving the unique one. $O(n)$ time, $O(1)$ space. (2)

(d) $4\oplus1=5$; $5\oplus2=7$; $7\oplus1=6$; $6\oplus2=4$. Answer 4. (2)

Question 4 (12)

(a) Greedy rule: Shortest Processing Time first (SPT) — sort jobs by $t_i$ ascending. (2)

(b) Exchange argument. Consider any optimal schedule; suppose two adjacent jobs $a$ (in position $p$) then $b$ (position $p+1$) are out of order, i.e., $t_a > t_b$. Let $T$ = total processing time of all jobs before position $p$. Completion times of $a$ and $b$:

• Original: $C_a = T + t_a$, $C_b = T + t_a + t_b$. Their sum $= 2T + 2t_a + t_b$.
• Swapped ($b$ then $a$): $C_b' = T + t_b$, $C_a' = T + t_b + t_a$. Sum $= 2T + 2t_b + t_a$.

All other jobs' completion times unchanged (jobs before position $p$ unaffected; jobs after position $p+1$ see the same total $t_a+t_b$ preceding them). Difference in objective: $\Delta = (2T+2t_b+t_a) - (2T+2t_a+t_b) = t_b - t_a < 0 \quad\text{since } t_a>t_b.$ So swapping strictly decreases the objective — contradicting optimality unless no such inversion exists. Repeatedly removing adjacent inversions transforms any optimal schedule into SPT order without increasing cost; hence SPT is optimal. (8) (setup/assumption 2, completion-time algebra 3, Δ computation 2, conclusion 1)

(c) SPT order of $\{3,1,2\}$: $1,2,3$. Completion times: $1, 3, 6$. $\sum C_i = 1+3+6 = \mathbf{10}$. (2)

Question 5 (12)

(a) Table (rows = AXBY prefixes, cols = ABCY prefixes), $D[i][j]$:

Distance = 2 (substitute X→B... actually: align A,B,Y; edit AXBY→ABCY: substitute X→B then B→C? Two operations). Distance $=2$. (6) (recurrence/table 4, correct value 2)

(b) (i) Las Vegas — always produces correct sorted output; only runtime is random. (ii) Monte Carlo — fixed runtime but may give a wrong answer with bounded probability. (2)

(c) Trials independent, each errs $\le 1/2$ when $AB\ne C$; accept only if all pass, so error $\le (1/2)^t$. Need $(1/2)^t \le 0.001 \Rightarrow 2^t \ge 1000 \Rightarrow t \ge \log_2 1000 \approx 9.97 \Rightarrow t = \mathbf{10}$ (since $2^{10}=1024\ge1000$, $2^9=512<1000$). (4)

[
  {"claim":"Painting fence n=4,k=3 total is 66","code":"k=3\nsame={}; diff={}\nsame[2]=k; diff[2]=k*(k-1)\nfor i in range(3,5):\n    same[i]=diff[i-1]\n    diff[i]=(k-1)*(same[i-1]+diff[i-1])\ntotal=same[4]+diff[4]\nresult = (total==66)"},
  {"claim":"XOR of [4,1,2,1,2] equals 4","code":"from functools import reduce\nvals=[4,1,2,1,2]\nx=reduce(lambda a,b:a^b, vals)\nresult = (x==4)"},
  {"claim":"SPT order of {3,1,2} gives sum of completion times 10","code":"ts=sorted([3,1,2])\nt=0; s=0\nfor x in ts:\n    t+=x; s+=t\nresult = (s==10)"},
  {"claim":"Smallest t with (1/2)**t <= 0.001 is 10","code":"import math\nt=0\nwhile (Rational(1,2))**t > Rational(1,1000):\n    t+=1\nresult = (t==10)"},
  {"claim":"Edit distance AXBY vs ABCY is 2","code":"a='AXBY'; b='ABCY'\nm=len(a); n=len(b)\nD=[[0]*(n+1) for _ in range(m+1)]\nfor i in range(m+1): D[i][0]=i\nfor j in range(n+1): D[0][j]=j\nfor i in range(1,m+1):\n    for j in range(1,n+1):\n        c=0 if a[i-1]==b[j-1] else 1\n        D[i][j]=min(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1]+c)\nresult = (D[m][n]==2)"}
]