How to Think About Algorithms

There are many algorithm texts that provide lots of well-polished code and proofs of correctness. This book is not one of them. Instead, this book presents insights, notations, and analogies to help the novice describe and think about algorithms like an expert. By looking at both the big picture and easy step-by-step methods for developing algorithms, the author helps students avoid the common pitfalls. He stresses paradigms such as loop invariants and recursion to unify a huge range of algorithms into a few meta-algorithms. Part of the goal is to teach the students to think abstractly. Without getting bogged with formal proofs, the book fosters a deeper understanding of how and why each algorithm works. These insights are presented in a slow and clear manner accessible to second- or third-year students of computer science, preparing them to find their own innovative ways to solve problems.

Table of Contents

PART ONE: Iterative Algorithms and Loop Invariants
Chapter 1 Iterative Algorithms: Measures of Progress and Loop Invariants
Chapter 2 Examples Using More-of-the-Input Loop Invariants
Chapter 3 Abstract Data Types
Chapter 4 Narrowing the Search Space: Binary Search
Chapter 5 Iterative Sorting Algorithms
Chapter 6 Euclid’s GCD Algorithm
Chapter 7 The Loop Invariant for Lower Bounds

PART TWO: Recursion
Chapter 8 Abstractions, Techniques, and Theory
Chapter 9 Some Simple Examples of Recursive Algorithms
Chapter 10 Recursion on Trees
Chapter 11 Recursive Images
Chapter 12 Parsing with Context-Free Grammars

PART THREE: Optimization Problems
Chapter 13 Definition of Optimization Problems
Chapter 14 Graph Search Algorithms
Chapter 15 Network Flows and Linear Programming
Chapter 16 Greedy Algorithms
Chapter 17 Recursive Backtracking
Chapter 18 Dynamic Programming Algorithms
Chapter 19 Examples of Dynamic Programs
Chapter 20 Reductions and NP-Completeness
Chapter 21 Randomized Algorithms

PART FOUR: Appendix
Chapter 22 Existential and Universal Quantifiers
Chapter 23 Time Complexity
Chapter 24 Logarithms and Exponentials
Chapter 25 Asymptotic Growth
Chapter 26 Adding-Made-Easy Approximations
Chapter 27 Recurrence Relations
Chapter 28 A Formal Proof of Correctness

PART FIVE: Exercise Solutions
Chapter Chapter 1. Iterative Algorithms: Measures of Progress and Loop Invariants
Chapter Chapter 2. Examples UsingMore-of-the-Input Loop Invariant
Chapter Chapter 3. Abstract Data Types
Chapter Chapter 4. Narrowing the Search Space: Binary Search
Chapter Chapter 6. Euclid’s GCD Algorithm
Chapter Chapter 7. The Loop Invariant for Lower Bounds
Chapter Chapter 8. Abstractions, Techniques, and Theory
Chapter Chapter 9. Some Simple Examples of Recursive Algorithms
Chapter Chapter 10. Recursion on Trees
Chapter Chapter 11. Recursive Images
Chapter Chapter 12. Parsingwith Context-Free Grammars
Chapter Chapter 14. Graph Search Algorithms
Chapter Chapter 15. Network Flows and Linear Programming
Chapter Chapter 16: Greedy Algorithms
Chapter Chapter 17. Recursive Backtracking
Chapter Chapter 18. Dynamic Programming Algorithms
Chapter Chapter 19. Examples of Dynamic Programs
Chapter Chapter 20. Reductions and NP-Completeness
Chapter Chapter 22. Existential and Universal Quantifiers
Chapter Chapter 23. Time Complexity
Chapter Chapter 24. Logarithms and Exponentials
Chapter Chapter 25. Asymptotic Growth
Chapter Chapter 26. Adding-Made-Easy Approximations
Chapter Chapter 27. Recurrence Relations