Algorithm Paradigms

Q1. (4 marks)

• Optimal substructure: an optimal solution to the problem contains within it optimal solutions to its subproblems. (1.5)
• Overlapping subproblems: the recursive solution revisits the same subproblems many times (a small number of distinct subproblems solved repeatedly). (1.5)
• Overlapping subproblems distinguishes DP from plain divide-and-conquer (D&C subproblems are typically disjoint, so caching gives no benefit). (1)

Q2. (4 marks)

• General recurrence: $T(n) = a\,T(n/b) + f(n)$. (1.5)
• For $T(n)=2T(n/2)+n$: $a=2, b=2$, so $n^{\log_b a} = n^{\log_2 2} = n^1 = n$. Since $f(n)=n=\Theta(n^{\log_b a})$, we are in Master Theorem Case 2. (1.5)
• Result: $T(n) = \Theta(n \log n)$. (1)

Q3. (4 marks)

• Recurrence: $F(n) = F(n-1) + F(n-2)$, base $F(0)=0, F(1)=1$; store computed values in a memo. (2)
• Memoized time: $O(n)$; space: $O(n)$. (1)
• Naive recursion is $O(\varphi^n)$ (exponential) — memoization removes repeated work. (1)

Q4. (5 marks) Capacity $W=10$. Items (value, weight):

• Item A: value 60, weight 10 → ratio 6
• Item B: value 100, weight 20... (must fit in 10; use valid example below)

Valid counter-example — capacity 10:

• A: v=6, w=1 (ratio 6)
• B: v=10, w=5 (ratio 2)
• C: v=10, w=5 (ratio 2)

Greedy takes A (ratio 6, w=1), then B or C (w=5), remaining capacity 4 unused for the other → value $6+10 = 16$. (2) Optimal takes B+C (w=10) → value $20$. (2) Since $16 < 20$, greedy by ratio fails. (1) (Any correct counter-example with greedy < optimal earns full marks.)

Q5. (4 marks) LCS of AGCAT (len 5) and GAC (len 3).

• Build DP: matches give subsequence GA or AC. (2)
• Length = 2. (1)
• One LCS: GA (or AC). (1)

Q6. (4 marks) Coins $\{1,3,4\}$, amount 6. Recurrence: $dp[x] = 1 + \min_{c \le x} dp[x-c]$, $dp[0]=0$. (2) Compute: $dp[3]=1, dp[4]=1, dp[6]=\min(dp[5],dp[3],dp[2])+1$. $dp[6]=dp[3]+1 = 2$ (coins 3+3). (1) Minimum coins = 2. (1)

Q7. (5 marks) Recurrence ($i,j$ = prefix lengths): $D[i][j]=\begin{cases}D[i-1][j-1] & A_i=B_j\\ 1+\min(D[i-1][j],\,D[i][j-1],\,D[i-1][j-1]) & \text{otherwise}\end{cases}$ with $D[i][0]=i,\ D[0][j]=j$. (2) kitten → sitting: substitute k→s, e→i, insert g at end = 3 operations. (3)

Q8. (4 marks) (a) XOR all elements; pairs cancel, leaving the single element. (1.5) (b) $13 = 1101_2$ → 3 set bits. (1.5) (c) x & (-x) (or x & (~x + 1)). (1)

Q9. (3 marks)

• Las Vegas: always returns a correct answer; running time is random. (1.5)
• Monte Carlo: runs in bounded time; answer may be wrong with some (bounded) probability. (1.5)

Q10. (3 marks)

• Exchange argument: assume an optimal solution differs from the greedy one; show you can swap an element of the optimal for a greedy choice without worsening the objective, transforming optimal into greedy step by step — hence greedy is also optimal. (2)
• Example: activity selection (or fractional knapsack / Huffman). (1)

[
  {"claim":"Master theorem: T(n)=2T(n/2)+n is Theta(n log n) — check f(n)=n^(log_b a)","code":"a,b=2,2; import sympy; expo=sympy.log(a,b); result = (sympy.simplify(expo)==1)"},
  {"claim":"Min coins for amount 6 with coins {1,3,4} is 2","code":"coins=[1,3,4]; N=6; INF=float('inf'); dp=[0]+[INF]*N\nfor x in range(1,N+1):\n    for c in coins:\n        if c<=x: dp[x]=min(dp[x], dp[x-c]+1)\nresult = (dp[6]==2)"},
  {"claim":"LCS length of AGCAT and GAC is 2","code":"A='AGCAT'; B='GAC'; m,n=len(A),len(B)\nd=[[0]*(n+1) for _ in range(m+1)]\nfor i in range(1,m+1):\n    for j in range(1,n+1):\n        d[i][j]=d[i-1][j-1]+1 if A[i-1]==B[j-1] else max(d[i-1][j],d[i][j-1])\nresult = (d[m][n]==2)"},
  {"claim":"Edit distance kitten -> sitting is 3","code":"A='kitten'; B='sitting'; m,n=len(A),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        D[i][j]=D[i-1][j-1] if A[i-1]==B[j-1] else 1+min(D[i-1][j],D[i][j-1],D[i-1][j-1])\nresult = (D[m][n]==3)"},
  {"claim":"Number of set bits in 13 is 3","code":"result = (bin(13).count('1')==3)"}
]