Skip to content

Course track

8 lessons for a graduate algorithms class of the CLRS and Erickson kind. It assumes nothing, starts at what a logarithm is, and ends at writing an NP-completeness proof that earns full marks.

Independent of the interview track. Start either one cold.

Interview trackCourse track
Deliverableworking code, fasta written proof
Judged ondoes it pass the testsis every claim justified
Typical answer30 lines of Pythona page of English and maths
Failure modeyou frozeyou hand-waved
  1. 21

    21 — The Course Track: Orientation

    18 min read

    21.1 What this material actually teaches · 21.2 How to study this material · 21.3 Using this file honestly · 21.4 How to write a proof that holds up · 21.5 Pseudocode conventions · 21.6 The mathematical toolkit you need on day one

  2. 22

    22 — Asymptotics from Zero

    28 min read

    22.1 Why we throw information away · 22.2 The five notations as a comparison system · 22.3 The definitions, unpacked term by term · 22.4 Proving a bound from the definition · 22.5 The limit method: the shortcut you will actually use · 22.6 The growth hierarchy

  3. 23

    23 — Recursion and Recurrences

    37 min read

    23.1 Recursion is induction run backwards · 23.2 Tower of Hanoi, derived from nothing · 23.3 Three more recursions, each derived by hand · 23.4 Where a recurrence comes from · 23.5 Method 1: the recursion tree · 23.6 Method 2: the master theorem

  4. 24

    24 — Divide and Conquer

    27 min read

    24.1 The pattern · 24.2 Mergesort · 24.3 Counting inversions · 24.4 Quicksort and the cost of a bad split · 24.5 Selection: the k-th smallest in linear time · 24.6 The sorting lower bound

  5. 25

    25 — Dynamic Programming

    21 min read

    25.1 What DP actually is · 25.2 The recipe · 25.3 The cut-and-paste argument · 25.4 Memoization vs bottom-up, and recovering the solution · 25.5 The canonical problems · 25.6 Writing the answer, worked end to end

  6. 26

    26 — Greedy Algorithms

    23 min read

    26.1 What greedy means · 26.2 The two proof techniques · 26.3 Activity selection, proved properly · 26.4 Scheduling to minimize lateness · 26.5 Huffman coding · 26.6 Minimum spanning trees

  7. 27

    27 — Graphs and Network Flow

    24 min read

    27.1 Vocabulary and representation · 27.2 Breadth-first search · 27.3 Depth-first search and its structure · 27.4 Topological sort · 27.5 Strongly connected components · 27.6 Shortest paths

  8. 28

    28 — NP-Completeness and Lower Bounds

    25 min read

    28.1 Setting up: decision problems and encodings · 28.2 Reductions · 28.3 Cook-Levin, and the shape of the field · 28.4 The standard NP-complete problems · 28.5 How to write an NP-completeness proof · 28.6 Choosing the right source problem