01744cam a2200181 a 4500008004100000020002400041041000800065080001500073100001800088245003400106260004800140300001500188505085300203520045501056650001501511650001501526650002101541080110s2008 enka 001 0 eng a9780521614108 (pbk) aeng a510.6bEDM1 aEdmonds, Jeff10aHow to Think about Algorithms aNew York bCambridge University Pressc2008 axiii, 448p aIterative 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 a"This book presents insights, notations, and analogies to help the novice describe and think about algorithms like an expert. Jeff Edmonds provides both the big picture and easy step-by-step methods for developing algorithms, while avoiding the common pitfalls. Paradigms such as loop invariants and recursion help to unify a huge range of algorithms into a few meta-algorithms. Part of the goal is to teach the students to think abstractly."--Jacket 0aAlgorithms 0aInvariants 0aRecursion theory