How to think about Algorithms
- Cambridge ; New York Cambridge University Press 2008
- xiii, 448 pages : illustrations ; 25 cm
Iterative 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 bounds -- Abstractions, techniques, and theory -- Some simple examples of recursive algorithms -- Recursion on trees -- Recursive images -- Parsing with context-free grammars -- Definition 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 algorithms -- Existential and universal quantifiers -- Time complexity -- Logarithms and exponentials -- Asymptotic growth -- Adding-made-easy approximations -- Recurrence relations -- A formal proof of correctness.
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.
9780521614108
Study and teaching, Invariants, Algorithms, Loops (Group theory), Recursion theory