From First Principles to Proven Programs — There is a particular kind of silence in a lecture hall when a student has understood something. Not the silence of confusion, which is heavy, but the quiet that arrives a half-second before someone says “oh — of course.” Every page of this book was written trying to earn that half-second.

Overview

Chapters 1 to 3 build the foundations: what an algorithm is, how to prove one correct, the RAM model, asymptotic notation, recurrences and the Master Theorem. Chapters 5 to 7 cover sorting, balanced search trees, divide and conquer, and dynamic programming. Chapters 9 to 11 turn to greedy algorithms and to graphs — searching them, and spanning them. Chapters 13 to 15 treat shortest paths, amortized analysis, and the all-pairs problem.

Chapters 4, 8, 12 and 16 are different in kind. Each is an Evaluation and Discussion chapter that closes one quarter of the book. Nothing new is introduced there; instead, the material of the three chapters before it is put to work on complete problems, solved in full: every problem restated in plain words, every step of the reasoning written out, the arithmetic shown, the tempting wrong turns named and taken apart, a second method given wherever one exists, and a complete program that was compiled and run. Each problem ends with a “check yourself” variant, so that you can test whether the method has become yours.

Every program in this book is complete, compiles with a standard C++17 compiler, and was run before its output was printed here. No output appears on these pages that a machine did not produce. The same programs are collected, chapter by chapter, in the accompanying Code folder, each with a README that explains how to compile and run it on Windows, macOS and Linux.

Inside the Book

1. Foundations, Framework, and First Problems
2. Getting Started: the RAM Model, Insertion Sort, and Searching
3. Asymptotic Notation, Recurrences, and the Master Theorem
4. Evaluation and Discussion I: Foundations, Analysis, and First Problems
5. Sorting in Practice: Heapsort and Quicksort
6. Binary Search Trees and AVL Trees
7. From Divide and Conquer to Dynamic Programming
8. Evaluation and Discussion II: Sorting, Search Trees, and Dynamic Programming
9. Greedy Algorithms
10. Elementary Graph Algorithms: Breadth-First and Depth-First Search
11. Minimum Spanning Trees, DAGs, and Topological Sort
12. Evaluation and Discussion III: Greedy Algorithms and Graphs
13. Single-Source Shortest Paths
14. Amortized Analysis
15. All-Pairs Shortest Paths
16. Evaluation and Discussion IV: Shortest Paths, Amortized Analysis, and the Whole Book