Splitting two n-digit integers in half still creates four recursive products and leaves the runtime at n². Karatsuba reconstructs the cross term with (a+b)(c+d)-ac-bd, cuts the branching factor to three, and reaches roughly n^1.585.
Lecture 2 turns 'fast' into a worst-case bound that can be proved. A loop invariant establishes InsertionSort's correctness while its worst case is n²; a recursion invariant and O(n) work per level give MergeSort O(n log n).
For T(n)=aT(n/b)+O(n^d), the central comparison is branching growth a versus per-problem shrinkage b^d. Equality makes every level equally heavy, a<b^d makes the root dominate, and a>b^d makes the leaves dominate; outside the template, use substitution.
Selection does not require sorting. Median of medians groups elements by five, selects the median of the group medians as a pivot, and guarantees that the larger recursive side has at most 7n/10+5 elements; substitution proves O(n) worst-case time.
Randomized QuickSort has O(n log n) expected time on every fixed input but Θ(n²) worst-case time. The valid proof does not substitute expected subproblem sizes into a recurrence; it computes the probability that each pair is compared.
The Ω(n log n) lower bound applies to comparison sorting. When integer keys can index buckets directly, stable Counting Sort can power Radix Sort and achieve O(n) under conditions such as M≤n^c.
Ordinary BST operations cost O(h) and can degrade to O(n); five red-black invariants cap the height at 2 log₂(n+1), giving search, insertion, and deletion worst-case O(log n) bounds.
A universal hash family only needs to keep the collision probability of every distinct key pair at most 1/n; that makes the expected bucket size below 2, yielding expected O(1), not per-operation worst-case O(1).
DFS and BFS both scan an adjacency-list graph in O(n+m); DFS finish times produce a topological order for a DAG, while BFS layers equal exact unweighted shortest-path distances.
Contracting each SCC always produces a DAG; first-pass DFS finish times order those components, and a second pass on the transposed orientation discovers exactly one SCC per DFS tree in O(n+m).
Dijkstra finalizes the minimum estimate and relies on nonnegative weights; Bellman-Ford repeatedly relaxes every edge, spending O(nm) to support negative edges and detect a negative cycle reachable from the source.
Dynamic programming starts by defining subproblems, derives a recurrence from optimal substructure, and evaluates states in dependency order; Bellman–Ford layers by edge count, while Floyd–Warshall layers by allowed intermediate vertices.
Lecture 13 turns dynamic programming into five steps: choose a state, derive transitions, fill the table, reconstruct a solution, and then improve the implementation. LCS takes O(mn), both knapsack variants take O(nW) pseudo-polynomial time, and maximum-weight independent set on a tree takes O(|V|).
A greedy algorithm is not merely 'pick what looks best.' It keeps one choice at each step and needs an exchange argument proving that the choice preserves an optimum. Lecture 14 develops that proof pattern through activity selection, weighted completion time, and Huffman coding.
The heart of MST algorithms is an invariant: the selected edges remain contained in some MST. The cut property proves that every step of Prim and Kruskal is safe.
Ford–Fulkerson augments through a residual network. When no path remains, residual reachability yields a cut equal to the flow, certifying max flow, min cut, and their equality.
Deferred Acceptance permits tentative choices to be revoked. Monotone proposals prove O(n²) termination and stability, with an outcome favoring the proposing side.
The finale recaps the CS161 toolbox and points toward LP duality, Reed–Solomon coding, and ML-assisted algorithms. Officially, this lecture has slides but no notes.