Milestone map
Milestone map
3 milestones
Master Loop Invariants and Formal Induction Proofs
8–14 weeks (after study of discrete mathematics fundamentals)
Study formal methods for proving algorithm correctness: loop invariants, structural induction, and mathematical induction. Apply these to at least five standard algorithms — binary search, insertion sort, merge sort, and two others of your choice. For each algorithm, write a formal correctness proof using the loop invariant method: initialisation, maintenance, and termination.
Proof required
Submit: five formal correctness proofs (one per algorithm) each following the loop invariant structure — initialisation (invariant holds before first iteration), maintenance (if it holds before iteration k, it holds before iteration k+1), and termination (invariant implies correctness when loop terminates). Each proof must be submitted as a typed document. Submit to a CS lecturer, researcher, or experienced software engineer, who must confirm in writing that the proofs are formally valid.
What gets checked
- All five proofs follow the loop invariant structure with all three components — initialisation, maintenance, and termination
- A CS lecturer, researcher, or senior engineer with formal methods experience has confirmed in writing that the proofs are valid
- Proofs are typed and clearly structured — not handwritten notes
Common mistakes
- Writing informal correctness arguments ('the loop clearly terminates because...') rather than formal proofs — informality is not correctness
- Choosing only simple algorithms and avoiding the harder cases that require nested loop invariants
Resources
Foundationstart here
Depthgo deeper
What a verifier looks for
- Ask the candidate to prove the correctness of an algorithm they did not include in their submitted proofs — can they construct the proof in real time?
- For each submitted proof: does the initialisation hold? Is the maintenance step valid? Does termination follow?
- Ask: 'what happens to the loop invariant if the input is already sorted?' — challenges maintenance understanding
Prove Complexity Bounds and Reduction Correctness
8–12 weeks (after milestone 1)
Apply formal proof methods to computational complexity: prove Big-O, Omega, and Theta bounds for at least five algorithms using formal definitions (not asymptotic intuition). Additionally, prove at least one problem reduction — show that problem A reduces to problem B in polynomial time, and that correctness of the reduction follows formally.
Proof required
Submit: five formal complexity proofs (one per algorithm) each showing Big-O, Omega, and Theta bounds using the formal limit or constant-finding definition — not informal 'the inner loop runs n times' reasoning; and one formal problem reduction proof showing the reduction, its polynomial time bound, and its correctness. All six proofs must be reviewed and verified by a CS lecturer or researcher who confirms they are formally valid.
What gets checked
- Complexity proofs use the formal definition — finding constants c and n₀ such that the bound holds, not informal reasoning
- The problem reduction proof specifies the reduction, proves polynomial time, and proves correctness of the reduction
- A CS lecturer or researcher has confirmed all six proofs are formally valid in writing
Common mistakes
- Using informal reasoning ('O(n²) because there are two nested loops') instead of the formal definition
- Reduction proof that only describes the reduction without proving correctness — the proof must show the reduction preserves the problem's answer
Resources
Foundationstart here
Depthgo deeper
What a verifier looks for
- Select one complexity proof and ask: 'show me the formal derivation using constants c and n₀' — informal reasoning fails this
- For the reduction proof: 'if problem B is polynomial, prove problem A is polynomial through this reduction'
- Ask about the tightest known bound for one of the algorithms — does the candidate know the difference between upper bound and tight bound?
Prove Correctness of a Novel Algorithm
6–12 weeks (after milestone 2)
Design an algorithm to solve a problem not covered in any textbook or course materials you used — and formally prove its correctness and complexity. The algorithm must solve a well-specified problem. The proof must be reviewed and challenged by a CS lecturer or researcher in a live or recorded session.
Proof required
Submit: a well-specified problem statement; a description of the algorithm; a formal correctness proof; a formal complexity proof; and a recording or transcript of a live review session with a CS lecturer or researcher where they challenged at least one aspect of the proof and you responded.
What gets checked
- The problem is well-specified — preconditions, postconditions, and input/output contract are stated
- The algorithm is not taken from a known source — the design is original
- A CS lecturer or researcher challenged the proof in a documented live review — not just signed off on a submitted document
Common mistakes
- Choosing a problem so simple that the 'algorithm' is trivial and the proof requires no technique
- Live review that is a brief conversation without any genuine challenge to the proof
Resources
Foundationstart here
Depthgo deeper
What a verifier looks for
- Is the problem well-specified with preconditions, postconditions, and input/output contract?
- Is the algorithm genuinely original — not restatement of a known algorithm?
- Did the live review session include a genuine challenge to at least one part of the proof?