Stable Matching

Gale-Shapley algorithm, proofs of stability and optimality.

Greedy Algorithms

Interval scheduling, minimum spanning tree (Kruskal's, Prim's). Exchange arguments and greedy-stays-ahead proofs.

Dynamic Programming

Top-down, bottom-up styles. Bellman Ford, Segmented Least Squares

Divide and Conquer

Fast Fourier Transform, randomized median finding. Recurrences and the Master Theorem.

Network Flow

Ford-Fulkerson, max-flow min-cut theorem, bipartite matching, and reductions.

NP-Completeness

P vs. NP, polynomial-time reductions, NP-hard and NP-complete problems.

Computability

Turing Machines, Recognizability, Decidability, Halting Problem