stage 03 · Core
Algorithms & Data Structures
Choose representations from constraints, derive invariants and proofs, implement reliable algorithms, and test them against adversarial cases.
5 sections 40 units about 159 h 0/40
Sections
In dependency order
Capstone
Scheduler & Stream Algorithms Lab (8 to 12 h)
Review the stage through three small artifacts drawn from the Algorithms and Data Structures Laboratory. Keep the evidence compact enough to inspect, rerun and defend without completing another problem list.
Milestone deliverables
- Correctness library - hash map, mutable-priority heap, union-find, one graph routine and one reconstructing DP, each with an invariant and complexity note
- Failure evidence - generated operation histories, adversarial cases, minimized failures and repairs for at least two seeded defects
- Transfer and measurement - one unfamiliar problem solved cold plus one benchmark connecting asymptotic behavior, input distribution and memory locality
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Correctness library | A hash map, a mutable-priority heap, union-find, one graph routine and one reconstructing DP, each with its invariant, a complexity note and a test against an independent oracle, all run by one command. | Each structure has a stateful or property test over operation histories, and every invariant is also asserted in a debug mode. |
| Failure evidence | At least two seeded defects, each with the generated history or adversarial case that exposed it, the minimized failure and the repair. | Every minimized failure is kept as a regression test and mapped to the invariant it broke. |
| Transfer | One unfamiliar problem solved cold, with the invariant and bound written before code: a tag-hidden problem from the mini-projects or a new free LeetCode problem. | The cold solve records a rejected first idea and the counterexample that killed it. |
| Measurement | One benchmark connects asymptotic behavior, input distribution and memory locality, such as the hash map's probes across key distributions, or a NumPy gather through a shuffled index against a sequential one at sizes below and above the cache. | Predictions are written before measuring, and the benchmark shows the working-set effect across sizes. |
| Rebuild | A README lists the commands that rerun every test and benchmark. | One command reruns everything, with the setup needed to reproduce it stated. |
Capstone hours · 8 to 12
Begin the first section