Algorithms Illuminated

Part I. The Basics: 1. Introduction; 2. Asymptotic notation; 3. Divide-and-Conquer algorithms; 4. The master method; 5. QuickSort; 6. Linear-time selection; Part II. Graph Algorithms and Data Structures: 7. Graphs: the Basics; 8. Graph search and its applications; 9. Dijkstra's shortest-path algorithm; 10. The heap data structure; 11. Search trees; 12. Hash tables and Bloom filters; Part III. Greedy Algorithms and Dynamic Programming; 13. Introduction to greedy algorithms; 14. Huffman codes; 15. Minimum spanning trees; 16. Introduction to dynamic programming; 17. Advanced dynamic programming; 18. Shortest paths revisited; Part IV. Algorithms for NP-Hard Problems; 19. What is NP-Hardness?; 20. Compromising on correctness: efficient inexact algorithms; 21. Compromising on speed: exact inefficient algorithms; 22. Proving problems NP-hard; 23. P, NP, and all that; 24. Case study: the FCC incentive auction; Appendix A. Quick review of proofs By induction; Appendix B. Quick review of discrete probability; Epilogue. A field guide to algorithm design; Hints and solutions.