How to Think about Algorithms

Preface; Introduction; Part I. Iterative Algorithms and Loop Invariants: 1. Iterative algorithms: 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; 8. Key concepts summary: loop invariants and iterative algorithms; 9. Additional exercises: Part I; 10. Partial solutions to additional exercises: Part I; Part II. Recursion: 11. Abstractions, techniques, and theory; 12. Some simple examples of recursive algorithms; 13. Recursion on trees; 14. Recursive images; 15. Parsing with context-free grammars; 16. Key concepts summary: recursion; 17. Additional exercises: Part II; 18. Partial solutions to additional exercises: Part II; Part III. Optimization Problems: 19. Definition of optimization problems; 20. Graph search algorithms; 21. Network flows and linear programming; 22. Greedy algorithms; 23. Recursive backtracking; 24. Dynamic programming algorithms; 25. Examples of dynamic programming; 26. Reductions and NP-completeness; 27. Randomized algorithms; 28. Key concepts summary: greedy algorithms and dynamic programmings; 29. Additional exercises: Part III; 30. Partial solutions to additional exercises: Part III; Part IV. Additional Topics: 31. Existential and universal quantifiers; 32. Time complexity; 33. Logarithms and exponentials; 34. Asymptotic growth; 35. Adding-made-easy approximations; 36. Recurrence relations; 37. A formal proof of correctness; 38. Additional exercises: Part IV; 39. Partial solutions to additional exercises: Part IV; Exercise Solutions; Conclusion; Index.