A decision tree that sorts three items with at most three comparisonsAn array partitioned into values below, equal to and above a pivot

Independent study companion · CMU 15‑451/651 · follows the Fall 2026 public schedule

See the algorithm. Find the invariant. Defend the proof.

A visual, proof-first companion to an upper-level algorithms course. Watch algorithms change state step by step, write the code yourself, and finish with problems that do not tell you which technique to use.

Try module 1 — no signupSee the 15-451 map
25 modules · about 56 hoursFreeHands-on labs

Independent project. Not affiliated with or endorsed by Carnegie Mellon University.

How it works

After lecture, don't just reread the notes.

  1. See it

    Your own code draws its state as it runs, so you can watch the invariant hold, one frame at a time.

  2. Prove it

    Turn the picture into a correctness argument and a running-time bound, in the right model.

  3. Transfer it

    Solve a new problem that does not name the technique it needs.

The lab stops telling you which algorithm you are practising.

Every module ends with a mastery challenge: a short story that never names its technique. You choose the plan, say why it is correct and how fast it is, and then write it.

See it

The algorithm must be able to undo itself

Pushing flow path by path gets stuck at 8 on this network. The fix is a reverse residual arc: not an original pipe, but the right to cancel flow sent earlier. Step through it.

Open the network-flow module

These frames are the network-flow lesson's own figures, drawn with straightedge, the library your lab code draws with. In the lab, your code records frames like these as it runs.

The pipeline network with flow value 0. Pipes from s to t, each labelled flow/capacity. Push along any path with room: s a b d t can take 4.
Module 12 · frame 1 of 5Pipes from s to t, each labelled flow/capacity. Push along any path with room: s a b d t can take 4.

Start with one idea

Module 1 · Selection in Linear TimeWhy groups of five?Median of medians finds any rank in linear time. Groups of three look cheaper, but the proof stops working: see exactly where the recurrence breaks.Open the module Module 10 · Dynamic Programming ISeven decisions before you codeState, recurrence, base case, order, answer, reconstruction, space: the checklist that turns knapsack, tree DP and increasing subsequences into tables.Open the module Module 12 · Network Flow and MatchingsThe algorithm must be able to undo itselfA greedy flow gets stuck at 8. Residual arcs take flow back, and max-flow min-cut proves when you are done.Open the module

Following 15-451?

The Fall 2026 schedule, lecture by lecture

The modules follow the topics of the public Fall 2026 schedule of CMU 15-451/651, in the same order, with the date each lecture takes a topic up. Every lesson, example and exercise here is original. Every lecture has a module.

15-451 lecture (Fall 2026)SciMigo module
1 Introduction, Algorithm Analysis, Linear-time SelectionTue 25 Aug1. Selection in Linear Time
2 Concrete Models and Lower BoundsThu 27 Aug2. Lower Bounds and Adversaries
3 Integer Models and Integer SortingTue 1 Sep3. Integer Sorting
4 Hashing: Universal and Perfect HashingThu 3 Sep4. Universal and Perfect Hashing
5 FingerprintingTue 8 Sep5. Fingerprinting and String Matching
6 Range Query Data StructuresThu 10 Sep6. Range Queries and Segment Trees
7 Amortized AnalysisTue 15 Sep7. Amortized Analysis
8 Splay TreesThu 17 Sep8. Splay Trees
9 Union-FindTue 22 Sep9. Union-Find
10 Dynamic Programming IThu 24 Sep10. Dynamic Programming I
11 Dynamic Programming IITue 29 Sep11. Dynamic Programming II
12 Network Flows I: Flows, Cuts, and MatchingsThu 1 Oct12. Network Flow and Matchings
13 Network Flows II: Polynomial-time AlgorithmsTue 6 Oct13. Polynomial-Time Max Flow
14 Network Flows III: Minimum-cost FlowsThu 8 Oct14. Minimum-Cost Flow
15 Game TheoryTue 20 Oct15. Zero-Sum Games
16 Linear ProgrammingThu 22 Oct16. Linear Programming
17 Linear Programming II: DualityTue 27 Oct17. LP Duality
18 Linear Programming III: Integrality and PolytopesThu 29 Oct18. Polytopes and Integrality
19 General MatchingsThu 5 Nov19. General Matchings
20 Approximation AlgorithmsTue 10 Nov20. Approximation Algorithms
21 Online AlgorithmsThu 12 Nov21. Online Algorithms
22 Multiplicative Weights AlgorithmTue 17 Nov22. Multiplicative Weights
23 The Fast Fourier Transform AlgorithmThu 19 Nov23. The Fast Fourier Transform
24 Convolutions and their ApplicationsTue 24 Nov24. Convolutions and Their Applications
25 The Algorithmic Magic of PolynomialsTue 1 Dec25. Polynomials in Algorithm Design

Source: 15-451/651 Fall 2026 schedule, read 2026-09-27. Topic names are listed only to show what each module covers.

Found a technical error in a lesson or lab? Report a correction. Corrections are tracked in public.

Your Learning Path

Each module builds on the last. Open any published lesson or lab and continue at your own pace.

1

15-451 F26 · Lecture 1 · Tue 25 Aug

Selection in Linear Time — Find the median without sorting: with a guarantee, then with coins

Median of medians finds any rank in linear time, even in the worst case. See why groups of five make the standard proof work while groups of three leave that recurrence inconclusive, then swap the guarantee for a random pivot and measure both against sorting.

You build: An in-place partition, median of medians, and a robot dock placer

  • selection
  • invariants
  • recurrences
  • randomized algorithms
Free120 minReading materialInteractive lab
2

15-451 F26 · Lecture 2 · Thu 27 Aug

Lower Bounds and Adversaries — Prove that no comparison algorithm can do better

Count the leaves of a decision tree to show sorting needs log n! comparisons, then build an adversary that forces any algorithm to work hard, and meet its bound exactly.

You build: An adversary, a knockout tournament, and a ladder merger nobody can beat

  • lower bounds
  • decision trees
  • adversary arguments
Free110 minReading materialInteractive lab
3

15-451 F26 · Lecture 3 · Tue 1 Sep

Integer Sorting — Beat n log n by using keys as addresses

The n log n bound only holds for algorithms that compare. Use keys as array positions instead: counting sort, stable passes, and radix sort with the right base.

You build: Counting sort, radix sort, and a badge-log sorter under a comparison budget

  • counting sort
  • stability
  • radix sort
  • models of computation
Free105 minReading materialInteractive lab
4

15-451 F26 · Lecture 4 · Thu 3 Sep

Universal and Perfect Hashing — Let a coin pick the hash function, so no key set is bad

Every fixed hash function has a bad input. Draw the function at random and every input is fine on average; then build a two-level table that answers every lookup in two reads.

You build: A growing hash table and a blocklist that answers in two reads

  • universal hashing
  • expected cost
  • perfect hashing
Free135 minReading materialInteractive lab
5

15-451 F26 · Lecture 5 · Tue 8 Sep

Fingerprinting and String Matching — Compare huge things by their remainders

Two huge files can be compared by exchanging a few dozen bits, if the prime is random. Roll a fingerprint along a text, catch a false alarm, and build a matcher that is never wrong.

You build: A string matcher that is never wrong, and a copied-ledger detector

  • fingerprinting
  • random primes
  • Karp-Rabin
  • Las Vegas vs Monte Carlo
Free125 minReading materialInteractive lab
6

15-451 F26 · Lecture 6 · Thu 10 Sep

Range Queries and Segment Trees — Every node knows the answer for its block

Prefix sums collapse under updates. Build a tree where every node stores its block's answer, so any range takes two nodes per level and any update rewrites one path, for any associative operation.

You build: A segment tree for any operation, and a box office that books and finds seats fast

  • segment trees
  • invariants
  • monoids
  • range queries
Free135 minReading materialInteractive lab
7

15-451 F26 · Lecture 7 · Tue 15 Sep

Amortized Analysis — Paying for the expensive step with the cheap ones

One append can copy a million elements, yet a million appends cost under three million steps. Prove it three ways, design the potential that pays for shrinking too, and watch the half-full rule thrash.

You build: A growing and shrinking array, and a two-pile job broker

  • amortized cost
  • banker's method
  • potential functions
  • dynamic arrays
Free135 minReading materialInteractive lab
8

15-451 F26 · Lecture 8 · Thu 17 Sep

Splay Trees — No balance information, still O(log n) per operation, amortized

A single access can make Θ(n) rotations, yet any m accesses make at most m(3 log₂ n + 1) + log₂ n! in all. Rotate with zig, zig-zig and zig-zag, prove the Access Lemma from the rank potential, and build a full splay tree.

You build: A splay tree with split and join, and an extent map that learns its hot spots

  • splay trees
  • rotations
  • Access Lemma
  • amortized analysis
Free140 minReading materialInteractive lab
9

15-451 F26 · Lecture 9 · Tue 22 Sep

Union-Find — Short trees by size, shorter still by compression

Connectivity that only grows needs just two operations. Prove union by size keeps trees shallow, add path compression, meet the inverse-Ackermann bound, and use it to drive Kruskal.

You build: A union-find that drives Kruskal, and a leak detector for a porous tile

  • union-find
  • union by size
  • path compression
  • Kruskal
Free125 minReading materialInteractive lab
10

15-451 F26 · Lecture 10 · Thu 24 Sep

Dynamic Programming I — Seven decisions that turn a search into a table

Knapsack, independent sets on trees and longest increasing subsequences each become a table once you name the state, recurrence, base case, order, answer, reconstruction and space.

You build: A knapsack table you can walk back, a tree DP, and a crate-nesting planner

  • dynamic programming
  • knapsack
  • tree DP
  • increasing subsequences
Free140 minReading materialInteractive lab
11

15-451 F26 · Lecture 11 · Tue 29 Sep

Dynamic Programming II — Shortest paths between every pair, and tours through every city

Floyd–Warshall finds every cheapest path, negative edges included; Held–Karp finds an optimal tour by remembering only which cities you visited. Prove both, and measure n²·2ⁿ against n!.

You build: All-pairs shortest paths with routes, and an optimal night route for a museum robot

  • Floyd–Warshall
  • negative cycles
  • Held–Karp
  • bitmask DP
Free145 minReading materialInteractive lab
12

15-451 F26 · Lecture 12 · Thu 1 Oct

Network Flow and Matchings — Push flow, take it back, and find the cut that proves you are done

Pushing flow along paths gets stuck; residual arcs that take flow back fix it. Run Ford–Fulkerson, prove max-flow min-cut so every answer carries a certificate, and solve matching as a flow.

You build: A max-flow solver with its certificate, and a reviewer-assignment planner

  • max flow
  • residual graphs
  • min cut
  • bipartite matching
Free125 minReading materialInteractive lab
13

15-451 F26 · Lecture 13 · Tue 6 Oct

Polynomial-Time Max Flow — Shortest augmenting paths, level graphs, and bounds that ignore the capacities

A plausible path rule takes 14,000 one-unit steps on a four-vertex network. Prove shortest augmenting paths never get shorter, group them into Dinic's blocking-flow phases, and bound the phases whatever the capacities.

You build: A Dinic max-flow solver with current-arc pointers, and an evening courier dispatcher

  • Edmonds–Karp
  • Dinic's algorithm
  • level graphs
  • unit-capacity bounds
Free130 minReading materialInteractive lab
14

15-451 F26 · Lecture 14 · Thu 8 Oct

Minimum-Cost Flow — The cheapest way to send it all, and the negative cycle that says you have not

When every unit has a price, send the required amount as cheaply as possible. Prove that a flow of the required value is cheapest exactly when its residual graph has no negative cycle, cancel cycles, then run successive shortest paths with potentials.

You build: A min-cost flow solver with potentials, and a clinic roster planner

  • min-cost flow
  • negative cycles
  • potentials
  • assignment problem
Free150 minReading materialInteractive lab
15

15-451 F26 · Lecture 15 · Tue 20 Oct

Zero-Sum Games — When the other side reads your plan, flip a coin, and know exactly which coin

The best defence against an opponent who knows your plan is a precise randomization. Solve games exactly with the opponent's strategy as a certificate, state the minimax theorem, and turn it into Yao's principle.

You build: An exact 2 × n game solver, and a night-guard schedule

  • zero-sum games
  • mixed strategies
  • minimax theorem
  • Yao's principle
Free130 minReading materialInteractive lab
16

15-451 F26 · Lecture 16 · Thu 22 Oct

Linear Programming — One modelling language for production plans, diets, flows and shortest paths

A surprising number of problems are linear programs. See why the optimum sits at a corner, walk the simplex method uphill from corner to corner, and model production, diets, flows and shortest paths exactly.

You build: An exact LP solver with standard-form conversion, and a data centre's power bill

  • linear programming
  • simplex method
  • standard form
  • LP modelling
Free125 minReading materialInteractive lab
17

15-451 F26 · Lecture 17 · Tue 27 Oct

LP Duality — When the optimum is finite, the best upper bound meets it, and the prices are the proof

Prices on a maximization LP's constraints give upper bounds, and when the LP has an optimum the best bound meets it. Prove weak duality in one line, certify a feasible pair by complementary slackness, and see minimax and min-cut as duality.

You build: A certificate checker for LP optima, and a proof a cooperative can check with a pencil

  • LP duality
  • complementary slackness
  • shadow prices
  • certificates
Free125 minReading materialInteractive lab
18

15-451 F26 · Lecture 18 · Thu 29 Oct

Polytopes and Integrality — Why LP answers are corners, when corners are whole numbers, and how long simplex can walk

A corner is where n independent constraints are tight. Watch Dantzig's rule walk 2^n − 1 corners of a Klee–Minty cube, prove bipartite matching LPs have only 0/1 corners, and meet total unimodularity.

You build: A fractional-to-integral matching rounder, and a clinic shift planner

  • polytopes
  • Klee–Minty
  • integrality
  • total unimodularity
Free140 minReading materialInteractive lab
19

15-451 F26 · Lecture 19 · Thu 5 Nov

General Matchings — When pairs have no sides: shrink the odd cycles, and prove nobody could do better

The search that finds augmenting paths in bipartite graphs misses some once odd cycles appear. Prove Berge's theorem, write Edmonds' blossom algorithm, and read a Tutte–Berge certificate off its final forest.

You build: A blossom-algorithm matcher that proves its answer, and a rope-team planner

  • general matching
  • augmenting paths
  • blossoms
  • Tutte–Berge
Free150 minReading materialInteractive lab
20

15-451 F26 · Lecture 20 · Tue 10 Nov

Approximation Algorithms — When the optimum is out of reach, prove how close you get on every instance

Greedy scheduling, LP rounding for vertex cover and tree doubling for metric tours, each with a worst-case ratio proved against a lower bound on the optimum you never compute.

You build: A scheduler, a vertex cover and a tour with proved ratios, and an ambulance-station planner

  • approximation ratio
  • list scheduling
  • LP rounding
  • metric TSP
Free140 minReading materialInteractive lab
21

15-451 F26 · Lecture 21 · Thu 12 Nov

Online Algorithms — Decide before the future arrives, and lose by a bounded factor

Rent or buy, move-to-front and paging: prove competitive ratios against an adversary who knows your rule, and meet the lower bound that says no deterministic pager can do better than k.

You build: Move-to-front with its potential, LRU and the offline optimum, and an idle-worker controller

  • competitive ratio
  • rent or buy
  • list update
  • paging
Free135 minReading materialInteractive lab
22

15-451 F26 · Lecture 22 · Tue 17 Nov

Multiplicative Weights — Shrink the weight of every adviser who errs, and stay close to the best in hindsight

Weighted majority, then multiplicative weights with regret O(√(T log n)) on every sequence of losses in [0, 1], a matching lower bound, and zero-sum games solved approximately by letting two learners play.

You build: Hedge with its regret bound, an approximate game solver, and a traffic router

  • experts problem
  • weighted majority
  • regret
  • zero-sum games
Free155 minReading materialInteractive lab
23

15-451 F26 · Lecture 23 · Thu 19 Nov

The Fast Fourier Transform — Evaluate at roots of unity, and n² multiplications become O(n log n)

Split a polynomial into even and odd halves, evaluate at roots of unity with butterflies, and invert the transform. Exact arithmetic modulo a prime, and why floating point fails at scale.

You build: An exact NTT and fast multiplication, and a tape-block restorer

  • FFT
  • roots of unity
  • convolution
  • number-theoretic transform
Free135 minReading materialInteractive lab
24

15-451 F26 · Lecture 24 · Tue 24 Nov

Convolutions and Their Applications — One convolution counts every total, shift and alignment at once

When values lie in a small range, one convolution counts all pairwise sums, scores a pattern at every shift and counts mismatches at every alignment, faster than the double loop once the lists outgrow the range.

You build: Sliding scores, sum counts and DNA mismatches by convolution, and a pulsar-timing counter

  • convolution
  • correlation
  • string matching
  • 3SUM
Free135 minReading materialInteractive lab
25

15-451 F26 · Lecture 25 · Tue 1 Dec

Polynomials in Algorithm Design — A nonzero polynomial has few roots, so one random point checks, recovers and decides

Check a product at one random point, recover lost shares by interpolation, test for a perfect matching with a determinant, and verify a matrix product in n² time with Freivalds' check.

You build: Root finding, share recovery, matching by determinant, and a nightly audit over a thin link

  • Schwartz–Zippel
  • interpolation
  • Reed–Solomon
  • Tutte matrix
Free145 minReading materialInteractive lab

Built for

Who this course helps

  • Students taking (or about to take) an upper-level algorithms class who want it to click
  • People who have done LeetCode and want to know why the tricks actually work
  • Self-taught programmers ready for the proof-and-analysis side of algorithms

What you leave with

A shelf of algorithms you wrote, watched, measured and can defend

  • Identify the invariant or inductive claim that drives a correctness proof
  • Analyze running time in the right model, and recognize when a lower bound makes it optimal
  • Solve problems that do not tell you which technique they need

Your own code draws its state as it runs, so an invariant stops being a word in a proof and becomes something you can watch hold, one frame at a time.

About This Course

You have probably met sorting, hashing and binary search before. This course is the next step: instead of memorising which trick goes with which problem, you learn to invent an algorithm, prove it correct, pin down exactly how fast it is, and say when nothing can do better.

Every module has two halves. First a lesson you read: one story, a picture of the algorithm at work, the one idea (the invariant) that makes it correct, and the argument for its speed. Then a lab that runs in your browser, where your own code draws what it is doing, frame by frame, so you can scrub back to the exact step where it went wrong. Checks tell you when it works, and hints are there when you are stuck.

Each lab ends with a mastery challenge: a little story (a warehouse robot, two chess clubs, a pile of badge logs) that never tells you which technique to use. Working that out is the point. New modules arrive as they are finished; the 15-451 map near the top of this page shows which topics are covered so far.

Topic list modeled on the public schedules of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025 and Fall 2026). All lessons, examples, code and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.

Prerequisites

  • A first data-structures course: lists, hash maps, trees, BFS
  • Comfort with proofs by induction (you will write plenty of them)
  • Basic Python: functions, lists, dictionaries, loops

What You Will Learn

  • Identify the invariant or inductive claim that drives a correctness proof, and write the proof
  • Analyze running time in the right model of computation, and recognize when a lower bound shows it is optimal
  • Build selection, hashing, segment trees, union-find, dynamic programs, flows and linear programs from scratch
  • Measure your own code and check that the numbers match the proof
  • Crack problems that do not tell you which technique they need

Algorithm Design and Analysis: frequently asked questions

What do I need to know before starting?

A first data-structures course (lists, hash maps, trees, BFS) and a bit of practice with proofs by induction. Basic Python is enough for the labs: no libraries, nothing fancy.

Is it free?

Yes. Every lesson and every lab is free, with no account needed. New modules are added as they are finished.

How long does a module take?

About two hours: half an hour or so to read the lesson, then the lab. Nobody has to do every module, so pick the ones you are here for.

What is a mastery challenge?

The last exercise in every lab. It is a short story (a warehouse robot, two chess clubs, a stack of badge logs) that never names the technique it needs. You pick the plan, say why it works and how fast it is, then write it.

What if I get stuck?

Every exercise has hints you can open one at a time, checks that say exactly what went wrong, and a worked example you can swap in (and swap back out).

Is it like a university algorithms class?

Its topics follow the public Fall 2026 schedule of CMU 15-451/651, and the map near the top of this page shows which lecture each module goes with and when that lecture is. Everything you read and solve here is original to SciMigo. It is an independent project, not affiliated with Carnegie Mellon University.

Will it help with my 15-451 homework?

It teaches the same kind of reasoning on original problems: finding the invariant, proving the bound, choosing a technique nobody names for you. It does not solve your course's homework, and your course's collaboration policy still applies.

Start now

Module 1: Selection in Linear Time

Find the median without sorting: with a guarantee, then with coins. About 120 minutes. Runs in your browser. Nothing to install, no account needed.

Start module 1 — free