Chapter 0 Preface¶
Chapter 1 Introduction¶
Chapter 2 Analyzing Problems: The Basics¶
Chapter 3 Dynamic Programming¶
Chapter 4 Sorting¶
- 4.1. Chapter Introduction: Sorting
- 4.2. Sorting Terminology and Notation
- 4.3. Insertion Sort
- 4.4. Bubble Sort
- 4.5. Selection Sort
- 4.6. The Cost of Exchange Sorting
- 4.7. Optimizing Sort Algorithms with Code Tuning
- 4.8. Shellsort
- 4.9. Mergesort Concepts
- 4.10. Implementing Mergesort
- 4.11. Quicksort
- 4.12. Heapsort
- 4.13. Binsort
- 4.14. Radix Sort
- 4.15. An Empirical Comparison of Sorting Algorithms
- 4.16. Lower Bounds for Sorting
- 4.17. Sorting Summary Exercises
Chapter 5 Searching¶
Chapter 6 Lower Bounds¶
Chapter 7 Probabilistic Algorithms¶
Chapter 8 Graphs¶
Chapter 9 Limits to Computing¶
- 9.1. Limits to Computing
- 9.2. Reductions
- 9.3. NP-Completeness
- 9.4. NP-Completeness Proofs
- 9.5. Circuit Satisfiability
- 9.6. Formula Satisfiability
- 9.7. 3-CNF Satisfiability
- 9.8. Reduction of SAT to 3-SAT
- 9.9. The Clique Problem
- 9.10. The Independent Set Problem
- 9.11. The Vertex Cover Problem
- 9.12. The Hamiltonian Cycle Problem
- 9.13. The Traveling Salesman Problem
- 9.14. Reduction of Circuit SAT to SAT
- 9.15. Reduction of 3-SAT to Clique
- 9.16. Reduction of Independent Set to Vertex Cover
- 9.17. Reduction of 3-SAT to Hamiltonian Cycle
- 9.18. Reduction of Clique to Independent Set
- 9.19. Reduction of Hamiltonian Cycle to Traveling Salesman
- 9.20. Coping with NP-Complete Problems
