Edmonds Jeff. How to Think About Algorithms

New York: Cambridge University Press, 2008. — 472 p. — ISBN: 978-0-511-41370-4.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.Iterative Algorithms and Loop InvariantsIterative Algorithms: Measures of Progress and Loop Invariants
Examples Using More-of-the-Input Loop Invariants
Abstract Data Types
Narrowing the Search Space: Binary Search
Iterative Sorting Algorithms
Euclid’s Gcd algorithm
The Loop Invariant for Lower BoundsRecursionAbstractions, Techniques, and Theory
Some Simple Examples of Recursive Algorithms
Recursion on Trees
Recursive Images
Parsing with Context-Free GrammarsOptimization ProblemsDefinition of Optimization Problems
Graph Search Algorithms
Network Flows and Linear Programming
Greedy Algorithms
Recursive Backtracking
Dynamic Programming Algorithms
Examples of Dynamic Programs
Reductions and Np-completeness
Randomized AlgorithmsExistential and Universal Quantifiers
Time Complexity
Logarithms and Exponentials
Asymptotic Growth
Adding-Made-Easy Approximations
Recurrence Relations
A formal Proof of CorrectnessExercise Solutions