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 topics

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
17 modules · about 37 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.

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 9 · 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 11 · 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 2025 schedule, lecture by lecture

The modules follow the topics of the public Fall 2025 schedule of CMU 15-451/651, in the same order. Every lesson, example and exercise here is original. 17 of 25 topics have a module so far.

15-451 lecture (Fall 2025)SciMigo module
1 Introduction, algorithm analysis, linear-time selection1. Selection in Linear Time
2 Concrete models and lower bounds2. Lower Bounds and Adversaries
3 Integer models and integer sorting3. Integer Sorting
4 Hashing: universal and perfect hashing4. Universal and Perfect Hashing
5 Fingerprinting5. Fingerprinting and String Matching
6 Range query data structures6. Range Queries and Segment Trees
7 Amortized analysis7. Amortized Analysis
8 Union-find8. Union-Find
9 Dynamic programming I9. Dynamic Programming I
10 Dynamic programming II10. Dynamic Programming II
11 Network flows I: flows, cuts and matchings11. Network Flow and Matchings
12 Network flows II: polynomial-time algorithms12. Polynomial-Time Max Flow
13 Network flows III: minimum-cost flows13. Minimum-Cost Flow
14 Game theory14. Zero-Sum Games
15 Linear programming15. Linear Programming
16 Linear programming II: duality16. LP Duality
17 Linear programming III: integrality and polytopes17. Polytopes and Integrality
18 Approximation algorithmsIn development
19 Online algorithmsIn development
20 Streaming algorithmsIn development
21 Computational geometry I: fundamentals and the convex hullIn development
22 Computational geometry II: randomized incremental algorithmsIn development
23 Splay treesIn development
24 The algorithmic magic of polynomialsIn development
25 The fast Fourier transformIn development

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

Your Learning Path

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

1

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 proof work and groups of three break it, 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

Lower Bounds and Adversaries — Prove that no 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

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

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

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

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

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

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
9

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
10

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
11

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
12

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
13

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 a flow is cheapest exactly when no negative cycle remains, 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
14

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
15

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
16

LP Duality — Every maximum has a matching minimum, and the prices are the proof

Prices on the constraints give an upper bound, and the best such bound meets the optimum exactly. Prove weak duality in one line, find certifying prices 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
17

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

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 schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). 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 2025 schedule of CMU 15-451/651, and the map near the top of this page shows which lecture each module goes with. 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