Skip to main content

Module Quiz

Complete this quiz after finishing all concept and practice pages.

Current Module Questions​

Question 1: Formal Big-O​

Prove that f(n) = 5 n^2 + 3 n + 7 = O(n^2) by exhibiting specific constants c and n0.

Answer: Take c = 15, n0 = 1. For n >= 1, 5 n^2 + 3 n + 7 <= 5 n^2 + 3 n^2 + 7 n^2 = 15 n^2.

Solution Walkthrough:

  1. Bound each lower-order term by the leading term multiplied by a constant (valid for n >= 1).
  2. Sum the bounds: 5 + 3 + 7 = 15.
  3. Declare c = 15 and n0 = 1.

Question 2: Asymptotic Distinctions​

Is f(n) = n log n in O(n^2)? In Theta(n^2)? Explain.

Answer: n log n = O(n^2) yes, because log n <= n for n >= 1, so n log n <= n^2. It is not Theta(n^2) because n log n / n^2 = log n / n -> 0, so no constant c > 0 satisfies n log n >= c n^2 for all large n. Therefore n log n = O(n^2) but not Omega(n^2).

Question 3: Summation Analysis​

Give a tight Theta bound for the total work of:

for i in range(n):
    for j in range(i):
        work()  # O(1)

Answer: Theta(n^2).

Solution Walkthrough:

  1. Inner loop runs i times.
  2. Total: sum_{i=0}^{n-1} i = n(n-1)/2.
  3. n(n-1)/2 = Theta(n^2).

Question 4: Master Theorem​

Solve T(n) = 4 T(n/2) + n using the Master Theorem.

Answer: T(n) = Theta(n^2).

Solution Walkthrough:

  1. a = 4, b = 2, so n^(log_b a) = n^2.
  2. f(n) = n = O(n^(2 - epsilon)) for any epsilon < 1.
  3. Case 1 applies: T(n) = Theta(n^2).

Question 5: Recursion Tree​

Solve T(n) = T(n/2) + T(n/3) + n (not master-theorem form).

Answer: T(n) = Theta(n).

Solution Walkthrough:

  1. Work at level 0 is n.
  2. Work at level 1 is n/2 + n/3 = 5n/6.
  3. Each level multiplies work by 5/6, a constant less than 1.
  4. Total is a geometric series summing to n / (1 - 5/6) = 6 n = Theta(n).

Question 6: Amortized Analysis​

Using aggregate analysis, show that n appends to a dynamic array with doubling cost O(n) total.

Answer: Total work = n element writes plus copy work during resizes. Resizes happen at sizes 1, 2, 4, ..., 2^k <= n, and copy size-2^i uses 2^i work. Total copy work <= 1 + 2 + 4 + ... + 2^(floor log n) <= 2 n. Total work <= n + 2 n = 3 n = O(n). Amortized cost per append is O(1).

Question 7: Loop Invariant​

State a useful loop invariant for the outer loop of insertion sort.

Answer: Before iteration j of the outer loop, A[0 .. j-1] is a sorted permutation of the original values at those positions.

Question 8: Recursive Correctness​

Why does a proof of recursive correctness usually require strong induction rather than ordinary induction?

Answer: Recursive calls may be on various smaller sizes (n-1, n/2, n/3, etc.). Strong induction assumes correctness for all smaller inputs at once, matching the reality that the function may recurse to any smaller size.

Question 9: Termination​

Give a terminating variant for Euclid's algorithm gcd(a, b) = gcd(b, a mod b) and explain why it is well-founded.

Answer: Variant b. Each recursive call replaces b by a mod b, which is strictly less than b whenever b > 0. Values are non-negative integers, well-founded, so the recursion terminates at b = 0.

Question 10: Divide and Conquer​

What is the recurrence for mergesort, and what does it solve to? Include the Master Theorem case used.

Answer: T(n) = 2 T(n/2) + n. a = 2, b = 2, n^(log_b a) = n, so f(n) = Theta(n^(log_b a)). Case 2 gives T(n) = Theta(n log n).

Question 11: Greedy with Exchange Argument​

Explain in your own words why the earliest-finish-time greedy is optimal for activity selection.

Answer: In any optimal solution sorted by finish time, let b_1 be its first activity. The greedy's first pick a_1 has finish time <= f(b_1) (it is the minimum). Replacing b_1 with a_1 in the optimal solution yields a valid same-size solution. The subproblem after removing activities incompatible with a_1 is the same kind of problem, so the argument recurses. Therefore greedy matches some optimal solution, hence is optimal.

Question 12: Greedy vs DP​

Give an instance where a greedy "take the largest ratio" rule fails for 0/1 knapsack.

Answer: Items (w, v) = (1, 60), (2, 100), (3, 120), capacity 5. Greedy by ratio picks items 1 and 2, value 160. Optimum picks items 2 and 3, value 220. Greedy fails because it commits locally without room for the better pair.

Question 13: DP State Design​

For the longest common subsequence of strings X[0..m-1] and Y[0..n-1], write the state, recurrence, base cases, and runtime.

Answer:

  • State: LCS(i, j) = length of the longest common subsequence of X[0..i-1] and Y[0..j-1].
  • Recurrence:
    • LCS(i, j) = 1 + LCS(i-1, j-1) if X[i-1] == Y[j-1]
    • LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)) otherwise
  • Base: LCS(0, j) = LCS(i, 0) = 0.
  • Runtime: Theta(m n) time and Theta(m n) space (reducible to Theta(min(m, n)) space).

Question 14: Memoization vs Tabulation​

Give one case where top-down memoization is strictly preferred to bottom-up, and one case where bottom-up is strictly preferred.

Answer:

  • Top-down preferred: sparse state space where only a small fraction of states are actually reached (e.g., a DP over (position, some rarely reached flag)).
  • Bottom-up preferred: dense state space with recursion depth exceeding language limits (T = 10^5 coin change in Python), or where space optimization (keeping only the last row of the table) matters.

Question 15: Paradigm Triage​

You are given n = 20 items with (weight, value) and a capacity W. Pick a paradigm and justify.

Answer: Either bitmask enumeration Theta(2^n) (about 10^6 operations, fits comfortably) or standard 0/1 knapsack DP Theta(n W). Bitmask is simpler and works when n <= 25. DP is preferred when W is small and n is large. Greedy does not apply because the 0/1 constraint breaks the exchange argument.

Interleaved Review Questions​

Prior Module Question 1 (S1 Module 1: Proof Techniques)​

Why is proof by example not a valid proof for a universal claim over natural numbers?

Answer: Checking finitely many instances does not rule out counterexamples elsewhere. A universal claim requires an argument covering every element of the domain.

Prior Module Question 2 (S1 Module 2: Combinatorics)​

How many binary strings of length n contain exactly k ones?

Answer: C(n, k) = n! / (k! (n-k)!). Choose which k positions hold the ones.

Prior Module Question 3 (S1 Module 3: Probability)​

State the linearity of expectation and explain why it does not require independence.

Answer: E[X + Y] = E[X] + E[Y] for any random variables X and Y. Expectation is a linear functional on the space of random variables; no independence is needed because the definition of expectation (sum over outcomes weighted by probability) splits linearly regardless of dependence.

Prior Module Question 4 (S1 Module 1: Induction)​

Prove by induction that sum_{i=1}^{n} i = n(n+1)/2.

Answer: Base n = 1: 1 = 1 * 2 / 2. Inductive step: assume sum_{i=1}^{k} i = k(k+1)/2. Then sum_{i=1}^{k+1} i = k(k+1)/2 + (k+1) = (k+1)(k+2)/2. QED.

Prior Module Question 5 (S1 Module 4: Problem Solving)​

State Polya's four steps for problem solving and briefly explain each.

Answer:

  1. Understand the problem: restate it, identify knowns and unknowns.
  2. Devise a plan: relate to known problems, pick a strategy.
  3. Carry out the plan: execute the chosen approach carefully.
  4. Look back: verify the result and reflect on what worked.

Self-Assessment and Remediation​

Mastery Level (90-100% correct):

  • Ready to advance to Module 2 with confidence.

Proficient Level (75-89% correct):

  • Review only the missed concept pages and redo two problems of each missed type.

Developing Level (60-74% correct):

  • Rework Practice 1 (complexity), Practice 2 (correctness), and the DP-related katas. Expect the recurrence and DP-state work to be the main gap.

Insufficient Level (<60% correct):

  • Return to the concept sequence. Most likely issue: you are pattern-matching paradigms without proving correctness. Restart with Cluster 2 (correctness) and build outward.