Analysis & Correctness
A 15-module path through analysis & correctness, in study order from foundations to the frontier.
Modules
- The RAM Model of Computation
- Measuring Running Time as a Function of Input Size
- Asymptotic Notation: Big-O, Omega, Theta
- Growth Rates and the Asymptotic Hierarchy
- Analyzing Loops by Counting Operations
- Best, Average, and Worst Case Analysis
- Expected Running Time and Randomized Analysis
- Loop Invariants and Correctness Proofs
- Correctness of Recursive Algorithms by Induction
- Setting Up Recurrence Relations
- The Substitution Method
- The Recursion-Tree Method
- Amortized Analysis: The Aggregate Method
- Amortized Analysis: Accounting and Potential Methods
- Comparison-Based Sorting Lower Bounds