Techniques for Designing and Analyzing Algorithms

1. Introduction and Mathematical Background. 1.1. Algorithms and Programs. 1.2. Definitions and Terminology. 1.3. Order Notation. 1.4. Mathematical Formulae. 1.5. Probability Theory and Random Variables. 1.6. Notes and References. Exercises. 2. Algorithm Analysis and Reductions. 2.1. Loop Analysis Techniques. 2.2. Algorithms for the 3SUM Problem. 2.3. Reductions. 2.4. Exact Analysis. 2.5. Notes and References. Exercises. 3. Data Structures. 3.1. Abstract Data Types and Data Structures. 3.2. Arrays, Linked Lists and Sets. 3.3. Stacks and Queues. 3.4. Priority Queues and Heaps. 3.6. Hash Tables. 3.7. Notes and References. Exercises. 4. Divide-and-Conquer Algorithms. 4.1. Recurrence Relations. 4.2. The Master Theorem. 4.3. Divide-and-Conquer Design Strategy. 4.4. Divide-and-Conquer Recurrence Relations. 4.5. Binary Search. 4.6. Non-dominated Points. 4.7. Stock Profits. 4.8. Closest Pair. 4.9. Multiprecision Multiplication. 4.10. Modular Exponentiation. 4.11. Matrix Multiplication. 4.12. QuickSort. 4.13. Selection and Median. 4.14. Notes and References. Exercises. 5. Greedy Algorithms. 5.1. Optimization Problems. 5.2. Greedy Design Strategy. 5.3. Interval Selection. 5.4. Interval Coloring. 5.5. Wireless Access Points. 5.6. A House Construction Problem. 5.7. Knapsack. 5.8. Coin Changing. 5.9. Multiprocessor Scheduling. 5.10. Stable Matching. 5.11. Notes and References. Exercises. 6 Dynamic Programming Algorithms. 6.1. Fibonacci Numbers. 6.2. Design Strategy. 6.3. Treasure Hunt. 6.4. 0-1 Knapsack. 6.5. Rod Cutting. 6.6. Coin Changing. 6.7. Longest Common Subsequence. 6.8. Minimum Length Triangulation. 6.9. Memoization. 6.10. Notes and References. Exercises. 7. Graph Algorithms. 7.1. Graphs. 7.2. Breadth-first Search. 7.3. Directed Graphs. 7.4. Depth-first Search. 7.5. Strongly Connected Components. 7.6. Eulerian Circuits. 7.7. Minimum Spanning Trees. 7.8. Single Source Shortest Paths. 7.9. All-Pairs Shortest Paths. 7.10. Notes and References. Exercises. 8. Backtracking Algorithms. 8.1. Introduction. 8.2. Generating all Cliques. 8.3. Sudoku. 8.4. Pruning and Bounding Functions. 8.5. 0-1 Knapsack Problem. 8.6. Traveling Salesperson Problem. 8.7. Branch-and-bound. 8.8. Notes and References. Exercises. 9. Intractability and Undecidability. 9.1. Decision Problems and the Complexity Class P. 9.2. Polynomial-time Turing Reductions. 9.3. The Complexity Class NP. 9.4. Polynomial Transformations. 9.5. NP-completeness. 9.6. Proving Problems NP-complete. 9.7. NP-hard Problems. 9.8. Approximation Algorithms. 9.9. Undecidability. 9.10. The Complexity Class EXPTIME. 9.11. Notes and References. Exercises. Bibliography. Index.