Mathematics / core
The mathematics of discrete algorithms
Analyze correctness and resource growth through recurrences, greedy structure, dynamic programming, and reductions.
Your route through mathematics
Follow the path or begin with a question. Every lesson is open.
Your place, at your pace. Progress is optional and saved only in this browser when available.
Read / explore / reason
Inside this module
Module 01 core
The mathematics of discrete algorithms
Analyze correctness and resource growth through recurrences, greedy structure, dynamic programming, and reductions.
- 01
Loop invariants and termination
Turn an iterative procedure into a proof with preserved assertions, exit conditions, and a well-founded progress measure.
29 min - 02
Asymptotic bounds and recurrence solving
State resource bounds with quantifiers, solve recurrences by expansion and induction, and account for input encoding.
30 min - 03
Divide and conquer and the master theorem
Read a recursion tree level by level, apply a precise master theorem, and recognize recurrences outside its scope.
31 min - 04
Greedy exchange arguments
Prove when an irrevocable local choice can replace part of an optimum, and build counterexamples when the objective changes.
30 min - 05
Dynamic programming and Bellman recurrences
Define sufficient states, derive optimal substructure, and evaluate overlapping subproblems in a justified order.
32 min - 06
Shortest-path optimality and potentials
Certify shortest distances with feasible labels, understand Dijkstra's nonnegative-weight assumption, and reweight edges without changing path order.
33 min - 07
Matroids and greedy optimality
Recognize hereditary independence and augmentation, prove weighted greedy optimality, and distinguish maximal sets from maximum ones.
34 min - 08
Randomized algorithms and expected cost
Keep inputs fixed while averaging internal choices, analyze randomized quicksort with indicators, and distinguish expected cost from error guarantees.
33 min - 09
Reductions and NP-completeness
Translate decision instances with a polynomial-time equivalence, prove certificate membership, and preserve the direction of hardness.
34 min - 10
Approximation ratios and inapproximability
Compare a feasible solution against a certified optimum bound, prove the vertex-cover factor two, and separate exact hardness from approximation barriers.
34 min