Foundations

How to state what an algorithm must do, prove that it does it and count what it costs: abstract data types, proofs and invariants, the mathematical toolkit, asymptotic notation, recursion, recurrences, amortized analysis and the probability that randomized methods rely on. Every later part leans on these tools.

2 of 8 topics ready, listed in reading order

Algorithms and abstract data typesWhat an algorithm is, how an abstract data type separates a contract from its implementation, and how the handbook specifies, traces and tests code.Planned

Proofs and loop invariantsInduction, strong induction and loop invariants used to prove iterative and recursive code correct.Planned

Mathematical toolkitSums, logarithms, floors and ceilings and harmonic numbers, each derived and checked by code, as every cost analysis uses them.Planned

Asymptotic analysisCounting steps, Big O, Omega and Theta, analysing loops, best, worst and average cases, and space complexity.Ready

RecursionBase cases, the call stack, recursion trees, memoization, Python's recursion limit and turning recursion into iteration.Planned

Recurrences and the master theoremSubstitution, recursion trees and the master theorem for divide-and-conquer running times, with the cases where it does not apply.Ready

Amortized analysisThe aggregate, accounting and potential methods on dynamic arrays, binary counters and stacks with multipop.Planned

Counting and probability for algorithmsCounting and the pigeonhole principle, expectation, indicator variables, linearity, harmonic numbers and tail bounds, as used for quicksort, hashing and skip lists.Planned