Algorithmic Thinking & Peak Finding in 1D and 2D
Professor of Electrical Engineering and Computer Science
53:21·2012·undergraduate level
Shows why plausible-looking O(n) 2D divide-and-conquer algorithms can silently fail correctness—and how proving an invariant rescues both correctness and O(n log n) runtime.
Opening lecture of MIT 6.006 analyzing 1D and 2D peak-finding algorithms: greedy ascent pitfalls, divide-and-conquer recurrences T(n) = T(n/2) + Θ(1), and subtle counterexamples when generalizing to grids.
Referenced inOpen Curriculum · OSSU Core Theory
Seminar notes & discussion
No public seminar notes on this lecture yet.