Prerequisite Diagnostic
Spend 35–50 minutes closed-book. This checks earlier recursion, counting, binary-search, graph and proof skills; no DP algorithm is assumed. Keep an attempt before reading the feedback. There is no speed-based passing score.
| Task | What to produce |
|---|---|
| D1: recursion | For f(0)=0; f(n)=1+f(n-1), give a decreasing measure, result at 4, and maximum call depth |
| D2: subsets | List all indexed subsets of two equal-valued items. Explain why equal values do not erase identity |
| D3: boundary search | In [2,4,4,9], find the first position with value at least 4 and the first with value greater than 4 |
| D4: graph order | Give a topological order for 0->2,1->2,2->3. Explain what adding 3->1 changes |
| D5: costs | Count iterations of nested loops i=1..n, j=1..i; compare storing W with allocating W cells |
| D6: induction | Prove that the sum of the first n odd positive integers is n² using a base and inductive step |
| D7: constraints | For half-open intervals [0,2),[2,4),[1,3), list compatible pairs |
Feedback and repair
- D1: measure n decreases by one; result 4; five active calls including f(0). Revisit recursion and stack cost in Algorithm Analysis if these are confused.
- D2:
{},{0},{1},{0,1}. Equal-valued items can both be selected when they are distinct objects. Repair subset enumeration before knapsack tests. - D3: zero-based positions 1 and 3. Revisit lower/upper-bound contracts in Sorting and Searching; equality changes which boundary is found.
- D4:
0,1,2,3or1,0,2,3; the added edge creates a directed cycle. Revisit topological ordering in Graph Algorithms if an order is still claimed. - D5: n(n+1)/2 iterations. Binary encoding of W requires O(log(W+1)) bits, while W cells require storage proportional to W times cell size.
- D6: base n=0 gives 0=0. Assuming n², add next odd integer 2n+1 to obtain
(n+1)². Repair proof by induction before recurrence proofs. - D7: only the first two are compatible; equality of finish/start is allowed.
Repair every missed prerequisite and solve a changed instance without the key. Record what changed in your explanation. Start the main lessons once each prerequisite is independently explainable; the module teaches state design itself.