Lecture 2 decomposes search into a problem, frontier, and priority: UCS uses paid cost, Greedy uses estimated remaining cost, and A* combines them as `f=g+h`; tree and graph search require different optimality conditions.
The first slide of CS161 names three goals: design, analysis, communication. The third one is why handwritten homework scores zero and why solutions have to read like a memo to a colleague. Of the eight problem sets, HW2 is the wall. The lecture notebooks exist to show that timing runs can't tell you which algorithm is faster. And the summer offering is a completely different course wearing the same number.
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.
AI Engineer coding interviews aren't identical to SWE — beyond LeetCode medium, you'll face ML-flavored problems (implementing a tokenizer, writing a batch inference pipeline, handling sparse matrices). Strategy: practice LeetCode medium to 70% pass rate, then spend remaining time on numpy/pandas operations, data processing pipelines, and ML-related programming problems.