Prerequisite Diagnostic
Allow 35–50 minutes closed-book. These questions use earlier ordering, graph, array, arithmetic and proof skills; amortized or advanced-tree mastery is not assumed. Preserve an attempt before reading feedback.
| Task | Required response |
|---|---|
| D1: global ordering | Root 10 has left child 5 with right child 12. Explain whether all left-subtree keys are below 10 |
| D2: interval convention | For [2,4,6,8], compute sum over [1,3) and over [2,2) |
| D3: identity | Explain how equal keys differ in a unique-key map and a heap multiset |
| D4: graph reachability | After undirected edges 0-1,1-2 on four vertices, list components and a path from 0 to 2 |
| D5: geometric sum | Derive 1+2+4+...+2^j and compare its growth to j |
| D6: probability | If each of n events has probability at most p, give an upper bound on any event occurring, without assuming independence |
| D7: aliasing | Two roots share a child object. Explain what mutating that child's value does to both views |
Feedback and repair
D1 fails: 12 is in the left subtree of 10. D2 gives 10 and 0. D3 maps
replace a value for an existing key; heaps can retain repeated equal priorities.
D4 components are {0,1,2} and {3}, and path 0-1-2 is a graph witness.
D5 sum is 2^(j+1)-1, exponential in j. D6 union bound is at most
min(1,n*p). D7 both roots observe the mutated shared child unless a new
node/version was created; copying only roots does not isolate mutation.
Repair ordering/identity using Sorting and Searching, graph reachability using Graph Algorithms, geometric sums and induction using Algorithm Analysis, and union bounds using Probability. Draw aliasing explicitly before persistence. Recheck missed skills on changed inputs without this key; begin the main path once every prerequisite is independently explainable.