Stanford CS161 Lecture 18: From the Algorithmic Toolbox to LP, Coding, and ML

🌏 中文版

This is article nineteen in Reading Stanford CS161, covering Winter 2026 Lecture 18, taught by Ellen Vitercik on March 11, 2026; the official Winter 2026 course homepage defines the term and sequence used here. The component says What's next? and the deck says What we’ve done and what’s to come.

The source boundary is unusually important: the official component provides 52 slides and no lecture notes. I used the slides and component metadata, not Canvas or notes from another term.

Seventeen lectures in thirteen recap slides

The recap joins rigor and intuition: design algorithms, prove correctness, analyze worst-case time, and express growth with big-O. It revisits divide-and-conquer, randomized QuickSort, sorting bounds and RadixSort, trees, hashing, graphs, shortest paths, DP, greedy algorithms, flows, and Embedded EthiCS.

This is a recap, not a fresh set of complete pseudocode and proofs. DP retains overlapping subproblems, greedy commits after proving a choice safe, and max flow uses residual paths plus an equal-valued cut certificate. Technical details remain in the earlier lectures.

The algorithmic toolbox

Across the course, inputs shrink through divide-and-conquer, repeated states are retained through DP, and alternatives collapse through a proved greedy choice. Correctness uses induction, exchange arguments, cut certificates, residual reachability, and blocking-pair contradictions. Runtime analysis separates operation counts, numeric magnitudes, and computation models.

The randomized QuickSort recap fixes the input before randomness and distinguishes “always correct” from “usually fast.” Empirical speed and randomized choices do not replace proofs.

Linear programming and dual certificates

The primal example maximizes x+y subject to nonnegativity, 4x+y≤2, and x+2y≤1. Its optimum is 5/7. Combining the two constraints with w=1/7,z=3/7 proves every feasible solution has x+y≤5/7, and a feasible point attaining that value makes the bound tight.

The dual minimizes 2w+z subject to w,z≥0, 4w+z≥1, and w+2z≥1. The same weights form an optimality certificate. The slides connect this to max flow as primal and min cut as dual.

Because there are no lecture notes, and the slides name no concrete LP algorithm or asymptotic bound, this cannot be expanded into a claim that the lecture taught simplex, interior-point methods, or all degenerate, unbounded, and infeasible cases.

Polynomial interpolation and Reed–Solomon

The slides encode H,I,B,O,B as coefficients of f(x)=H+Ix+Bx²+Ox³+Bx⁴, transmit evaluations, and recover the polynomial despite some corrupted values. They point to fast divide-and-conquer interpolation and error correction.

This is a teaser. There is no recurrence, field assumption, error threshold, distance proof, or runtime—and no notes to supply them. Those details must not be attributed to Lecture 18.

ML for algorithm selection and design

For algorithm selection, graph features such as density and vertex count feed an ML model that chooses among algorithms A₁...A₈. The slides mention graph coloring and the 2016–17 FCC spectrum auction; without reading the cited study, this article does not enlarge the slide's simulation summary into an independent causal claim.

For design, the deck uses AlphaEvolve, labeled Science ’25, as an example. Its conclusion is still to ask whether an algorithm works, whether it is fast, and whether formal guarantees exist. The slides do not specify a general training objective, architecture, regret bound, or technical AlphaEvolve analysis.

The missing notes define the boundary

Again, Lecture 18 has slides only and no official notes. “17 lectures in 13 slides” describes the recap layout. LP, coding, and ML are road signs rather than complete chapters, and Winter 2026 course lists or announcements are not permanent facts.

This restraint matches the course's method: claims should follow evidence. The deck supports the displayed LP certificate but not a full LP runtime theorem; it supports an encoding intuition but not a decoding bound; it supports ML-assisted design as a direction but not replacing correctness proof with empirical output.

The three future gems share one thread

An LP dual solution, redundant Reed–Solomon evaluations, and the formal guarantees still required for ML-assisted algorithms come from different fields but return to one CS161 question: how can a result be verified? The LP example combines constraints into a numerical certificate bounding every feasible objective. The coding example adds structure so a receiver reconstructs rather than guesses. The ML example insists that a selected or generated algorithm must still answer correctness and speed questions.

The three segments have different technical depth. LP supplies a primal/dual numerical example that can be checked line by line. Polynomial coding supplies an encoding flow but no decoding threshold. ML supplies a feature-to-algorithm pipeline and examples but no generalization or regret bound. Article length cannot substitute for source strength: formulas can be expanded where shown, while directional teasers must retain their open boundaries.

This reconnects the course. Lecture 15 certified local choices with light edges, Lecture 16 certified global optimality with equal flow and cut, and Lecture 17 excluded blocking pairs through rejection history. Lecture 18 adds no complete new algorithm; it carries the demand for understandable guarantees into optimization, communication, and AI-assisted design.

A recap slide does not re-authorize every detail

The deck names the Master Method, randomized QuickSort, Bellman–Ford, Floyd–Warshall, LCS, Knapsack, Huffman, MST, and Ford–Fulkerson as pointers into the toolbox. It does not re-prove their recurrences, expected runtimes, cut properties, or max-flow min-cut theorem. This article therefore treats them as a course map rather than expanding each bullet into a new Lecture 18 technical claim.

Likewise, follow-on courses and Theory Lunch are Winter 2026 navigation. Readers should verify current offerings rather than treating the finale deck as a permanent schedule.

The same date boundary applies to research examples and citation years: this article preserves the lecture's record without claiming that it remains the latest state of the field.

Beyond the lecture

Natural next routes are optimization for LP algorithms and duality, coding theory for finite fields and decoding bounds, and learning-augmented algorithms for robust guarantees under prediction error. These are directions suggested by the deck, not material already taught in this lecture.

The best use of this finale is as a map: choose a tool here, then return to the earlier lecture for its full proof. Lecture 18 is intentionally a roadmap rather than a compressed substitute for every route.

References

• Lecture 18 anchor
• Lecture 18 slides — the only lecture PDF
• Official component metadata
• Stanford CS161 Winter 2026 course homepage — source for the term and series scope used here
• Lecture notes: the official component provides none; this article used no other term's notes.