How to Think About Algorithms

Textbook that teaches students how to think about algorithms like an expert, without getting bogged down in formal proof.

Jeff Edmonds (Author)

9780521614108, Cambridge University Press

Paperback, published 19 May 2008

472 pages, 156 b/w illus. 24 tables 203 exercises
23.3 x 17.7 x 2.4 cm, 0.75 kg

'… a great book to learn how to design and create new algorithms … a good book that the reader will appreciate in the first and subsequent reads, and it will make better developers and programmers.' Journal of Functional Programming

This textbook, for second- or third-year students of computer science, presents insights, notations, and analogies to help them describe and think about algorithms like an expert, without grinding through lots of formal proof. Solutions to many problems are provided to let students check their progress, while class-tested PowerPoint slides are on the web for anyone running the course. By looking at both the big picture and easy step-by-step methods for developing algorithms, the author guides students around the common pitfalls. He stresses paradigms such as loop invariants and recursion to unify a huge range of algorithms into a few meta-algorithms. The book fosters a deeper understanding of how and why each algorithm works. These insights are presented in a careful and clear way, helping students to think abstractly and preparing them for creating their own innovative ways to solve problems.

Part I. Iterative Algorithms and Loop Invariants: 1. Measures of progress and loop invariants
2. Examples using more of the input loop invariant
3. Abstract data types
4. Narrowing the search space: binary search
5. Iterative sorting algorithms
6. Euclid's GCD algorithm
7. The loop invariant for lower bounds
Part II. Recursion: 8. Abstractions, techniques, and theory
9. Some simple examples of recursive algorithms
10. Recursion on trees
11. Recursive images
12. Parsing with context-free grammars
Part III. Optimization Problems: 13. Definition of optimization problems
14. Graph search algorithms
15. Network flows and linear programming
16. Greedy algorithms
17. Recursive backtracking
18. Dynamic programming algorithms
19. Examples of dynamic programming
20. Reductions and NP-completeness
21. Randomized algorithms
Part IV. Appendix: 22. Existential and universal quantifiers
23. Time complexity
24. Logarithms and exponentials
25. Asymptotic growth
26. Adding made easy approximations
27. Recurrence relations
28. A formal proof of correctness
Part V. Exercise Solutions.

Subject Areas: Algorithms & data structures [UMB]