Chapter 25 Further Reading: Algorithm Design Strategies

Books

  • Cormen, T. H., et al. (2022). Introduction to Algorithms, 4th ed. MIT Press. Part IV covers divide and conquer, Part V covers greedy algorithms (including Huffman coding and matroid theory), and Part VI covers dynamic programming. The definitive treatment.

  • Kleinberg, J. & Tardos, E. (2005). Algorithm Design. Addison-Wesley. An excellent alternative to CLRS that emphasizes the design aspect. Chapters 4-6 cover greedy, divide and conquer, and DP with many worked examples and intuitive explanations.

  • Dasgupta, S., Papadimitriou, C., & Vazirani, U. (2006). Algorithms. McGraw-Hill. A concise and beautifully written algorithms textbook. Freely available online. Chapters 5-6 cover greedy and DP with a focus on insight over mechanics.

  • Wirth, N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. While it does not use the terms "greedy" or "dynamic programming" (both became standard terminology after this book), Wirth's approach to algorithm design embodies these strategies throughout.

Online Resources

  • Dynamic Programming Visualizations. visualgo.net/en/dp. Interactive visualizations of the knapsack, LCS, and other DP problems, showing how the table is filled.

  • MIT OpenCourseWare 6.006: Introduction to Algorithms. Lectures on dynamic programming by Erik Demaine are widely considered the best DP lectures available. Free on YouTube.

Historical Context

  • Bellman, R. (1957). Dynamic Programming. Princeton University Press. The book that launched dynamic programming as a field. Bellman named the technique "dynamic programming" partly because the word "dynamic" sounded impressive to government funders.

  • Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." The greedy shortest-path algorithm. A masterclass in proving that a greedy approach is optimal.

Topics for Further Exploration

  • Huffman Coding: A greedy algorithm for optimal prefix-free encoding. Used in data compression (ZIP, GZIP, JPEG).

  • Backtracking and Branch-and-Bound: Strategies for problems where greedy fails and DP's table is too large. Used in constraint satisfaction, game trees, and combinatorial optimization.

  • Approximation Algorithms: For NP-hard problems (where no polynomial-time exact algorithm is known), approximation algorithms find solutions within a provable factor of optimal.

  • Amortized Analysis: A technique (covered in Chapter 26) that complements these strategies by analyzing the average cost of operations over a sequence, rather than the worst case of any single operation.