Level 1 — RecognitionAlgorithm Paradigms

Algorithm Paradigms

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Chapter: 3.7 Algorithm Paradigms Level: 1 — Recognition (MCQ + Matching + True/False with justification) Time Limit: 20 minutes Total Marks: 30

Section A — Multiple Choice (1 mark each)

Q1. The recurrence $T(n) = 2T(n/2) + O(n)$ describes which classic paradigm and running time?

(a) Greedy, $O(n)$
(b) Divide and conquer, $O(n \log n)$
(c) Dynamic programming, $O(n^2)$
(d) Brute force, $O(2^n)$

Q2. Which proof technique is most associated with establishing the correctness of a greedy algorithm?

(a) Loop invariant
(b) Exchange argument
(c) Pumping lemma
(d) Amortized analysis

Q3. For the fractional knapsack problem, the correct greedy criterion is to sort items by:

(a) weight ascending
(b) value descending
(c) value-to-weight ratio descending
(d) value-to-weight ratio ascending

Q4. Which pair of properties must a problem exhibit for dynamic programming to apply?

(a) Overlapping subproblems and optimal substructure
(b) Greedy-choice property and matroid structure
(c) Independence and randomness
(d) NP-hardness and completeness

Q5. The time complexity of the standard $O(n \log n)$ Longest Increasing Subsequence algorithm relies on:

(a) hashing
(b) binary search on a "tails" array
(c) matrix exponentiation
(d) union-find

Q6. In Huffman coding, at each step the algorithm merges:

(a) the two nodes with the largest frequencies
(b) the two nodes with the smallest frequencies
(c) any two adjacent nodes
(d) the root with a leaf

Q7. The expression n & (n - 1) evaluates to:

(a) $n$ with its lowest set bit cleared
(b) $n$ with all bits flipped
(c) the number of set bits in $n$
(d) the lowest set bit isolated

Q8. A Monte Carlo randomized algorithm is characterized by:

(a) always correct, running time random
(b) possibly incorrect, running time bounded
(c) always correct and always fast
(d) deterministic output and deterministic time

Q9. Bitmask DP for the Travelling Salesman Problem has time complexity:

(a) $O(n!)$
(b) $O(2^n \cdot n^2)$
(c) $O(n^3)$
(d) $O(n \log n)$

Q10. The main difference between memoization and tabulation is that memoization is:

(a) bottom-up and iterative
(b) top-down and recursive
(c) always faster
(d) unable to store results

Section B — Matching (1 mark each, Q11 = 5 marks)

Q11. Match each problem to its most appropriate paradigm/complexity. Write the letter next to each number.

Problem		Answer choice
1. Edit distance (Levenshtein)		A. Backtracking with pruning
2. N-Queens		B. Greedy, $O(n \log n)$ after sorting
3. Activity selection		C. DP, $O(mn)$ table
4. Matrix chain multiplication		D. Isolate lowest set bit
5. `n & (-n)`		E. DP, $O(n^3)$

Section C — True/False WITH Justification (2 marks each: 1 verdict + 1 justification)

Q12. "The greedy algorithm always produces an optimal solution for the 0/1 knapsack problem." — True or False? Justify.

Q13. "Backtracking explores a state-space tree and can abandon (prune) a partial candidate as soon as it cannot lead to a valid solution." — True or False? Justify.

Q14. "Brute force / exhaustive search is acceptable only when the input size is large." — True or False? Justify.

Q15. "A Las Vegas algorithm may return an incorrect answer but always terminates quickly." — True or False? Justify.

Q16. " $a \oplus a = 0$ and $a \oplus 0 = a$ , which is why XOR can find the single unpaired element in an array where every other element appears twice." — True or False? Justify.

Q17. "In coin change with unlimited coins, the greedy 'take largest coin first' approach gives the minimum coin count for every possible coin system." — True or False? Justify.

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (b). Master theorem case: $a=2, b=2, f(n)=O(n)$ gives $n^{\log_2 2}=n$ , tied case ⇒ $O(n\log n)$ . This is merge sort's recurrence. (1)

Q2 — (b). Exchange argument transforms any optimal solution stepwise into the greedy one without worsening it, proving greedy optimality. (1)

Q3 — (c). Fractional knapsack: fill by highest value density (ratio) first; fractions allowed makes this exchange-optimal. (1)

Q4 — (a). DP requires optimal substructure (optimal solution built from optimal sub-solutions) and overlapping subproblems (same subproblems recur). (1)

Q5 — (b). Maintain array of smallest possible tail values of increasing subsequences; binary search each element ⇒ $O(n\log n)$ . (1)

Q6 — (b). Huffman greedily merges the two least-frequent nodes so rare symbols get longer codes. (1)

Q7 — (a). Subtracting 1 flips the lowest set bit and all trailing zeros; ANDing clears that lowest set bit. (1)

Q8 — (b). Monte Carlo: fixed (bounded) runtime, may err with small probability. (1)

Q9 — (b). States = (subset mask, current city) = $2^n\cdot n$ , each transition $O(n)$ ⇒ $O(2^n n^2)$ . (1)

Q10 — (b). Memoization = top-down recursion + memo cache; tabulation = bottom-up iteration. (1)

Q11 (5 marks, 1 each): 1 → C (edit distance = DP $O(mn)$ ) 2 → A (N-Queens = backtracking with pruning) 3 → B (activity selection = greedy after sorting by finish time) 4 → E (matrix chain = DP $O(n^3)$ ) 5 → D (n & -n isolates lowest set bit)

Section C (2 marks each: verdict 1 + justification 1)

Q12 — False. (1) Greedy by ratio can fail for 0/1 knapsack because items cannot be split; a high-ratio light item may block a better combination. Counter-example: capacity 10, items (value/weight) = (60,10), (100,20 no)… e.g. items {(w=1,v=6),(w=10,v=50)} cap 10: greedy by ratio picks the ratio-6 item then can't fit the big one, missing the optimum. (justification 1)

Q13 — True. (1) Backtracking builds partial solutions along a state-space tree and prunes a branch when a constraint is already violated, avoiding exploring its whole subtree. (1)

Q14 — False. (1) Brute force is acceptable only for small inputs (or small solution spaces) because exhaustive search cost grows exponentially/factorially; large inputs make it infeasible. (1)

Q15 — False. (1) A Las Vegas algorithm is always correct but its running time is random (may vary). The description given (may be wrong, always fast) describes Monte Carlo, not Las Vegas. (1)

Q16 — True. (1) XOR is associative/commutative; pairs cancel to 0 and $x\oplus 0 = x$ , so XOR-ing all elements leaves the single unpaired one. (1)

Q17 — False. (1) Greedy is optimal only for canonical coin systems (e.g. standard currency). Counter-example: coins {1,3,4}, amount 6 — greedy gives 4+1+1 = 3 coins, but optimal is 3+3 = 2 coins. (1)

[
  {"claim":"Master theorem: 2T(n/2)+O(n) is Theta(n log n) — verify log base 2 of 2 = 1 (tied case)","code":"result = (log(2,2) == 1)"},
  {"claim":"n & (n-1) clears lowest set bit: 12 & 11 == 8","code":"result = (12 & 11) == 8"},
  {"claim":"n & -n isolates lowest set bit: 12 & -12 == 4","code":"result = (12 & -12) == 4"},
  {"claim":"XOR pairs cancel: 5^3^5^3^7 == 7","code":"result = (5 ^ 3 ^ 5 ^ 3 ^ 7) == 7"},
  {"claim":"Coin change {1,3,4} amount 6: greedy=3 coins, optimal=2 coins","code":"greedy=0; amt=6\nfor c in [4,3,1]:\n    while amt>=c: amt-=c; greedy+=1\nresult = (greedy==3) and (3+3==6)"},
  {"claim":"TSP bitmask states 2^n * n for n=4 equals 64","code":"n=4; result = (2**n)*n == 64"}
]