A First Taste of Algorithms
What's in This Book
What's in This Book
This book is an introduction to algorithms — step-by-step methods for solving problems with a computer — and to the ideas behind machine learning. Each chapter takes one idea, shows why it works, and asks what it costs. Here is what each chapter covers:
Chapter 1: Two Questions. How to find something in a list quickly, and the two questions this book asks about every method — does it always work, and how much work does it take?
Chapter 2: The Greedy Idea. Solving a problem by always grabbing the best-looking option right now: when that works (fitting the most events into one day) and when it fails (making change with odd coins).
Chapter 3: The Procedure That Calls Itself. Recursion — solving a problem by having it call a smaller copy of itself. The Towers of Hanoi puzzle, merge sort, and how to count what a recursive method costs.
Chapter 4: Recursion That Remembers. How letting a method remember answers it has already worked out can turn a hopelessly slow procedure into a fast one.
Chapter 5: Maps, Mazes, and Networks. Graphs — dots joined by lines. Finding your way out of a maze, and finding the shortest route across a map.
Interlude: The Other Exponential. A short break: why computers kept getting faster for decades, and what that has to do with this book.
Chapter 6: Order, and Its Price. Putting things in order: why some sorting methods are far faster than others, and a proof that none can ever beat a certain speed limit.
Chapter 7: The Algorithm That Flips Coins. Using chance on purpose — why a method that makes random choices can be both fast and dependable, plus the surprising birthday coincidence.
Chapter 8: Learning as an Algorithm. The first machine-learning ideas: making predictions from examples, and improving a guess by taking small steps downhill.
Chapter 9: Building the Learner. Putting the pieces together to build a small learning machine from scratch, using the same kind of math behind the AI tools you already use.
Epilogue: The Edge of the Map. Two famous questions at the very limits of computing: one problem no computer can ever solve, and one that nobody yet knows how to.
Questions to talk about
No answer key. These are for arguing over, with someone who read the same chapter.
- Every chapter takes one idea, shows why it works, and asks what it costs. Why would a book insist on the cost every single time?
- Scan the nine chapter summaries. Which one sounds least like something a computer would need, and why do you think it is in here?
- The last chapter promises one problem no computer can ever solve. Before you read it, guess what kind of problem that could possibly be.
All 32 chapters of A First Taste of Algorithms · Foundations · All courses