Algorithm Paradigms

Question 1

(a) (5 marks) Greedy strategy: sort activities by finish time ascending; repeatedly pick the next activity whose start time $\ge$ finish time of the last chosen activity. (2)

sort activities by f ascending          # O(n log n)
last_finish = -inf ; count = 0
for (s, f) in activities:                # O(n)
    if s >= last_finish:
        select it; count += 1
        last_finish = f
return count

(2) Complexity: sorting dominates at $O(n\log n)$; the single linear scan is $O(n)$, so total $O(n\log n)$. (1)

(b) (9 marks) Greedy-choice lemma: Let $a_1$ be the activity with the earliest finish time. Then there exists an optimal solution that includes $a_1$. (1)

Proof by exchange: Let $O$ be any optimal solution, ordered by finish time, with first activity $a_j$. If $a_j = a_1$ done. Otherwise since $a_1$ has the minimum finish time, $f_{a_1} \le f_{a_j}$. (2) Form $O' = (O \setminus \{a_j\}) \cup \{a_1\}$. Feasibility: $a_1$ finishes no later than $a_j$, and every other activity in $O$ started after $f_{a_j} \ge f_{a_1}$, so no new overlap is created — $O'$ is a valid non-overlapping set. (3) Cardinality: $|O'| = |O|$, so $O'$ is also optimal and contains $a_1$. (1) Induction: Having fixed $a_1$, the remaining problem is activity selection on activities that start after $f_{a_1}$ — the same problem on a smaller set. By induction the greedy choices on the subproblem are optimal, and combined with $a_1$ give a globally optimal set. Hence greedy is optimal. (2)

(c) (6 marks) Counter-example (durations objective): three activities $A=[0,5]$ (duration 5), $B=[1,2]$ (1), $C=[2,3]$ (1). (2) Earliest-finish-first picks $B$ then $C$ (finishes 2, then 3), total duration $1+1 = 2$; it cannot then add $A$ (overlaps). (2) But choosing $\{A\}$ alone gives duration $5 > 2$. So earliest-finish is not optimal for the weighted/duration objective. (1) The paradigm that solves weighted interval scheduling optimally is Dynamic Programming (sort by finish, DP with binary search for last compatible interval). (1)

Question 2

(a) (6 marks) Recurrence (house-robber form): $M(i) = \max\big(M(i-1),\; M(i-2) + r_i\big)$ Base cases: $M(0)=0$, $M(1)=\max(0, r_1)$. (Allowing to skip negative rewards.) (3) Optimal substructure: an optimal choice for cells $1..i$ either excludes $i$ (reduces to optimal on $1..i-1$) or includes $i$ (then $i-1$ excluded, reduces to optimal on $1..i-2$); the overall optimum is built from optima of these subproblems. (2) Overlapping subproblems: a naive recursion recomputes $M(i-2)$ inside both $M(i-1)$ and $M(i)$, so the same subproblems recur exponentially often — motivating memoization/tabulation. (1)

(b) (5 marks)

prev2 = 0                     # M(0)
prev1 = max(0, r[1])          # M(1)
for i in 2..n:
    cur = max(prev1, prev2 + r[i])
    prev2 = prev1 ; prev1 = cur
return prev1

Time $O(n)$: one pass, $O(1)$ work per cell. (2) Space $O(1)$: only two rolling variables kept instead of the full $M[\cdot]$ table, because $M(i)$ depends only on the two previous values. (3)

(c) (5 marks) $r = [3,2,7,10,-1,8]$ (1-indexed).

• $M(0)=0$
• $M(1)=\max(0,3)=3$
• $M(2)=\max(M(1),\,M(0)+2)=\max(3,2)=3$
• $M(3)=\max(M(2),\,M(1)+7)=\max(3,10)=10$
• $M(4)=\max(M(3),\,M(2)+10)=\max(10,13)=13$
• $M(5)=\max(M(4),\,M(3)-1)=\max(13,9)=13$
• $M(6)=\max(M(5),\,M(4)+8)=\max(13,21)=\mathbf{21}$

$M(6)=21$. (4) Selected cells: indices 1, 3, 6 → rewards $3+10+8 = 21$ (non-adjacent). (1)

(d) (6 marks) Induction on $i$. Base: $M(0)=0$ and $M(1)=\max(0,r_1)$ are optimal by inspection (empty vs single). (1) Hypothesis: $M(k)$ is optimal for all $k<i$. (1) Step: Consider any optimal selection $S$ over $1..i$. Case 1: $i\notin S$. Then $S$ is a valid selection over $1..i-1$, so its value $\le M(i-1)$. (1) Case 2: $i\in S$. Then $i-1\notin S$ (adjacency), so $S\setminus\{i\}$ is a valid selection over $1..i-2$ with value $\le M(i-2)$; hence $\text{val}(S) \le M(i-2)+r_i$. (2) Thus every optimal $S$ has value $\le \max(M(i-1), M(i-2)+r_i)$, and both branches are achievable, so equality holds: $M(i)=\max(M(i-1),M(i-2)+r_i)$. (1)

Question 3

(a) (6 marks) Let the multiset be values where each of $\{v_1,\dots,v_k\}$ appears twice and $u$ appears once. XOR is commutative and associative, so we may reorder freely. (2) Group the pairs: each pair contributes $v_j \oplus v_j = 0$. (2) Total $= (v_1\oplus v_1)\oplus\dots\oplus(v_k\oplus v_k)\oplus u = 0\oplus 0 \oplus\dots\oplus u$. Using $a\oplus 0 = a$ repeatedly, the result is $u$. Hence the XOR of all elements equals the unique value. (2)

(b) (6 marks) Expression: x & (-x) (equivalently x & (~x + 1)). (2) Proof: Write $x$ in binary; let its lowest set bit be at position $p$, so $x = A\,1\,0^{p}$ where $0^p$ are $p$ trailing zeros and $A$ is the higher bits. In two's complement $-x = \sim x + 1$. Complementing flips all bits; adding 1 propagates a carry through the trailing zeros of $x$ (which are ones in $\sim x$) up to position $p$. (2) Result: below position $p$, both $x$ and $-x$ have zeros; at position $p$ both have a 1; above position $p$, the bits of $-x$ are the complement of $x$'s. ANDing: positions $<p$ give 0, position $p$ gives $1$, positions $>p$ give $A_i \wedge \overline{A_i} = 0$. So x & -x $= 2^p$, exactly the lowest set bit. (2)

(c) (6 marks) Each trial errs (says "prime" for a composite) with probability $\le \tfrac12$; trials independent. All $t$ trials wrong ⇒ wrong final answer, so $P(\text{error}) \le \left(\tfrac12\right)^t = 2^{-t}.$ (2) Require $2^{-t} \le 10^{-3} \Rightarrow t \ge \log_2 1000 = 3\log_2 10 \approx 9.966$, so smallest integer $t = \mathbf{10}$. (Check: $2^{-10}=1/1024 < 10^{-3}$; $2^{-9}=1/512 > 10^{-3}$.) (2) Contrast: This is Monte Carlo — fixed/bounded running time but a small probability of an incorrect answer (one-sided error here). A Las Vegas algorithm is always correct; its randomness affects only the running time, which becomes a random variable (e.g., expected-time bound). Trade-off: Monte Carlo risks correctness for guaranteed time; Las Vegas guarantees correctness at the cost of variable time. (2)

[
  {"claim":"M(6)=21 for house-robber recurrence on [3,2,7,10,-1,8]",
   "code":"r=[3,2,7,10,-1,8]\nfrom sympy import Max\nM=[0, Max(0,r[0])]\nfor i in range(2,7):\n    M.append(Max(M[i-1], M[i-2]+r[i-1]))\nresult = (M[6]==21)"},
  {"claim":"Selected non-adjacent cells 1,3,6 give reward 21",
   "code":"r=[3,2,7,10,-1,8]\nresult = (r[0]+r[2]+r[5]==21)"},
  {"claim":"Smallest t with 2**-t <= 1e-3 is 10",
   "code":"vals=[t for t in range(1,20) if 2**(-t)<=1e-3]\nresult = (min(vals)==10)"},
  {"claim":"lowest set bit x & (-x) equals 2**p for sample x=待 e.g. 12 -> 4",
   "code":"x=12\nresult = ((x & (-x))==4)"}
]