Algorithm Paradigms

Question 1 (10 marks)

(a) (3, one mark each)

• Divide: split the problem into smaller subproblems (usually of size $n/b$).
• Conquer: solve each subproblem recursively (base case solved directly).
• Combine: merge subproblem solutions into the solution for the original problem.

(b) (4) Master Theorem form $T(n)=aT(n/b)+f(n)$ with $a=2$, $b=2$, $f(n)=\Theta(n)$.

• Compute $n^{\log_b a} = n^{\log_2 2} = n^1 = n$. (1)
• Compare $f(n)=\Theta(n)$ with $n^{\log_b a}=n$: they are the same order → Case 2. (2)
• Result: $T(n) = \Theta(n^{\log_b a}\log n) = \Theta(n\log n)$. (1)

(c) (3) $a=4$, $b=2$, $f(n)=\Theta(n)$.

• $n^{\log_b a}=n^{\log_2 4}=n^2$. (1)
• $f(n)=\Theta(n)$ grows slower than $n^2$ (polynomially smaller) → Case 1. (1)
• $T(n)=\Theta(n^2)$. (1)

Question 2 (12 marks)

(a) (4) Greedy choice: pick the activity with the earliest finish time among compatible activities. (1 for the rule)

sort activities by finish time
last_finish = -infinity
count = 0
for each activity (s, f) in sorted order:
    if s >= last_finish:
        select it; count += 1
        last_finish = f
return count

(3 for correct pseudocode: sort by finish, compare start to last finish, update)

(b) (6) Exchange argument:

• Let $a_1$ be the greedy choice (earliest finishing activity). Let $O$ be an optimal solution. (1)
• If $a_1 \in O$, done. Otherwise let $a_j$ be the activity in $O$ with the earliest finish time. (1)
• Since $a_1$ finishes no later than any other activity, $f(a_1) \le f(a_j)$. (1)
• Form $O' = (O \setminus \{a_j\}) \cup \{a_1\}$. Because $a_1$ finishes no later than $a_j$, it does not overlap any activity in $O$ that started after $a_j$ finished, so $O'$ is still a valid (non-overlapping) set. (2)
• $|O'| = |O|$, so $O'$ is also optimal and contains the greedy choice. By induction on the remaining subproblem (activities starting after $f(a_1)$), greedy is optimal. (1)

(c) (2) Sorting dominates: $O(n\log n)$ for the sort, then $O(n)$ single pass ⇒ total $O(n\log n)$. (1 answer, 1 justification)

Question 3 (8 marks)

(a) (5) Counter-example: capacity $W=10$. Items: item A $(w=6, v=12)$, item B $(w=5, v=9)$, item C $(w=5, v=9)$.

• Ratios: A $=2.0$, B $=1.8$, C $=1.8$. (1)
• Greedy takes A first (ratio 2.0, value 12, remaining capacity 4). Neither B nor C fits (each weighs 5). Greedy total $=12$. (2)
• Optimal: take B + C: weight $10 \le 10$, value $= 18$. (2)
• Greedy 12 < optimal 18 ✓. (any valid counter-example earns full marks)

(b) (3) In fractional knapsack you may take any fraction of an item, so you can always fill capacity exactly by topping up with a fraction of the next-best-ratio item — the greedy exchange never leaves wasted capacity. In 0/1 knapsack items are indivisible, so committing to a high-ratio item can waste capacity and block a better combination; there is no exchange argument that preserves optimality. (3)

Question 4 (12 marks)

(a) (3) $\text{minCoins}(0)=0,\qquad \text{minCoins}(a)=1+\min_{c\in \text{coins},\,c\le a}\text{minCoins}(a-c)$ and $\text{minCoins}(a)=\infty$ if no coin can complete $a$. (2 recurrence, 1 base case)

(b) (5)

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount        # dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

(marks: dp init & base case 1, outer loop 1, inner loop over coins 1, correct transition 1, return/INF handling 1)

(c) (4) coins = [1,3,4], amount 6:

• dp[1]=1 (1); dp[2]=2 (1+1); dp[3]=1 (3); dp[4]=1 (4); dp[5]=min(dp[4],dp[2],dp[1])+1 = 2 (4+1); dp[6]=min(dp[5],dp[3],dp[2])+1 = min(2,1,2)+1 = 2 (3+3). (3 for table)
• Answer: 2 coins (3+3 or 4+1+1... but 3+3=2 is minimum). (1)

Question 5 (10 marks)

(a) (3) $LCS(i,j)=\begin{cases}0 & i=0 \text{ or } j=0\\ LCS(i-1,j-1)+1 & X_i=Y_j\\ \max(LCS(i-1,j),\,LCS(i,j-1)) & X_i\ne Y_j\end{cases}$ (1 base, 1 match, 1 mismatch)

(b) (4) X="AGCAT" (rows), Y="GAC" (cols). DP table (rows 0..5 for X prefix, cols 0..3 for Y prefix):

LCS length = 2 (e.g. "AC" or "GA"). (3 table, 1 answer)

(c) (3) $ED(i,j)=\begin{cases}i & j=0\\ j & i=0\\ ED(i-1,j-1) & X_i=Y_j\\ 1+\min(ED(i-1,j),ED(i,j-1),ED(i-1,j-1)) & X_i\ne Y_j\end{cases}$ (2) For "cat" vs "cut": only middle char differs (a→u), one substitution ⇒ edit distance = 1. (1)

Question 6 (8 marks)

(a) (3) XOR all elements together. XOR is commutative/associative, $x\oplus x=0$, and $x\oplus 0=x$. Each duplicated value cancels to 0, leaving only the unique element. (2 explanation, 1 property)

(b) (3) Lowest set bit: x & (-x) (equivalently x & (~x + 1)). (1) In two's complement $-x = \sim x + 1$, which flips all bits above the lowest set bit and matches only at the lowest set bit position, so the AND isolates exactly that one bit. (2)

(c) (2) Brian Kernighan: repeatedly do x = x & (x - 1) (clears the lowest set bit) and count iterations until x == 0. Runs in $O(k)$ where $k$ = number of set bits. (1 algorithm, 1 complexity)

[
  {"claim":"Merge sort recurrence T(n)=2T(n/2)+n gives Theta(n log n): log_b a = 1 equals exponent of f", "code":"a=2; b=2; import sympy; lba=sympy.log(a,b); result = (lba==1)"},
  {"claim":"T(n)=4T(n/2)+n has n^{log_2 4}=n^2 dominating linear f -> Theta(n^2)", "code":"import sympy; result = (sympy.log(4,2)==2)"},
  {"claim":"Greedy 0/1 knapsack counterexample: cap 10, item A(6,12), B(5,9), C(5,9); greedy=12, optimal=18", "code":"cap=10; greedy=12; optimal=9+9; result = (greedy==12 and optimal==18 and optimal>greedy)"},
  {"claim":"min coins for coins [1,3,4] amount 6 is 2", "code":"coins=[1,3,4]; amount=6; INF=float('inf'); dp=[0]+[INF]*amount\nfor a in range(1,amount+1):\n    for c in coins:\n        if c<=a and dp[a-c]+1<dp[a]: dp[a]=dp[a-c]+1\nresult = (dp[6]==2)"},
  {"claim":"LCS length of AGCAT and GAC is 2", "code":"X='AGCAT'; Y='GAC'; m=len(X); n=len(Y)\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 X[i-1]==Y[j-1] else max(d[i-1][j],d[i][j-1])\nresult = (d[m][n]==2)"},
  {"claim":"edit distance cat vs cut is 1", "code":"X='cat'; Y='cut'; m=len(X); n=len(Y)\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 X[i-1]==Y[j-1] else 1+min(d[i-1][j],d[i][j-1],d[i-1][j-1])\nresult = (d[m][n]==1)"}
]