Problems on Algorithms

Cover Page 1 License Agreement 2 First Edition 3 Contents 4 Preface 10 1. Introduction 12 1.1 How to Use This Book 12 1.2 Overview of Chapters 12 1.3 Pseudocode 14 1.4 Useful Texts 15 2. Mathematical Induction 19 2.1 Summations 19 2.2 Inequalities 21 2.3 Floors and Ceilings 21 2.4 Divisibility 22 2.5 Postage Stamps 22 2.6 Chessboard Problems 23 2.7 Fibonacci Numbers 25 2.8 Binomial Coefficients 25 2.9 What is Wrong? 26 2.10 Graphs 27 2.11 Trees 28 2.12 Geometry 29 2.13 Miscellaneous 30 2.14 Hints 31 2.15 Solutions 32 2.16 Comments 34 3. Big-O and Big-Omega 39 3.1 Rank the Functions 39 3.2 True or False? 41 3.3 Proving Big-O 42 3.4 Manipulating Big-O 43 3.5 Alternative Definitions 44 3.6 Find the Functions 45 3.7 Hints 46 3.8 Solutions 46 3.9 Comments 47 4. Recurrence Relations 48 4.1 Simple Recurrences 48 4.2 More Difficult Recurrences 49 4.3 General Formulae 50 4.4 Recurrences with Full History 50 4.5 Recurrences with Floors and Ceilings 51 4.6 Hints 52 4.7 Solutions 52 4.8 Comments 55 5. Correctness Proofs 57 5.1 Iterative Algorithms 57 5.1.1 Straight-Line Programs 58 5.1.2 Arithmetic 58 5.1.3 Arrays 60 5.1.4 Fibonacci Numbers 62 5.2 Recursive Algorithms 62 5.2.1 Arithmetic 63 5.2.2 Arrays 64 5.2.3 Fibonacci Numbers 65 5.3 Combined Iteration and Recursion 65 5.4 Hints 66 5.5 Solutions 67 5.6 Comments 69 6. Algorithm Analysis 70 6.1 Iterative Algorithms 70 6.1.1 What is Returned? 70 6.1.2 Arithmetic 72 6.1.3 Arrays 72 6.1.4 Fibonacci Numbers 73 6.2 Recursive Algorithms 73 6.2.1 Arithmetic 74 6.2.2 Arrays 74 6.2.3 Fibonacci Numbers 75 6.3 Combined Iteration and Recursion 75 6.4 Hints 75 6.5 Solutions 76 6.6 Comments 77 7. Divide-and-Conquer 78 7.1 Maximum and Minimum 78 7.2 Integer Multiplication 79 7.3 Strassen's Algorithm 84 7.4 Binary Search 85 7.5 Quicksort 86 7.6 Towers of Hanoi 88 7.7 Depth-First Search 89 7.8 Applications 90 7.9 Hints 92 7.10 Solutions 94 7.11 Comments 96 8. Dynamic Programming 98 8.1 Iterated Matrix Product 98 8.2 The Knapsack Problem 100 8.3 Optimal Binary Search Trees 101 8.4 Floyd's Algorithm 102 8.5 Applications 103 8.6 Finding the Solutions 108 8.7 Hints 110 8.8 Solutions 110 8.9 Comments 111 9. Greedy Algorithms 112 9.1 Continuous Knapsack 112 9.2 Dijkstra's Algorithm 113 9.3 Min-cost Spanning Trees 114 9.4 Traveling Salesperson 120 9.5 Applications 120 9.6 Hints 122 9.7 Solutions 122 9.8 Comments 126 10. Exhaustive Search 127 10.1 Strings 127 10.2 Permutations 129 10.3 Combinations 131 10.4 Other Elementary Algorithms 132 10.5 Backtracking 133 10.6 Applications 134 10.7 Hints 141 10.8 Solutions 142 10.9 Comments 144 11. Data Structures 146 11.1 Heaps 146 11.2 AVL Trees 149 11.3 2-3 Trees 152 11.4 The Union-Find Problem 153 11.5 Applications 153 11.6 Hints 156 11.7 Solutions 156 11.8 Comments 157 12. NP-Completeness 158 12.1 General 158 12.2 Cook Reductions 159 12.3 What is Wrong? 161 12.4 Circuits 163 12.5 One-in-Three 3SAT 164 12.6 Factorization 165 12.7 Hints 165 12.8 Solutions 166 12.9 Comments 166 13. Miscellaneous 167 13.1 Sorting and Order Statistics 167 13.2 Lower Bounds 168 13.3 Graph Algorithms 169 13.4 Maximum Flow 171 13.5 Matrix Reductions 172 13.6 General 173 13.7 Hints 175 13.8 Solutions 177 13.9 Comments 177 Bibliography 179 Index 185 Errata to the First Edition 191 Supplementary Problems 197 Mathematical Induction 198 Floors and Ceilings 211 Combinatorics 212 Probability 213 Asymptotics 220 Graph Problems 225 Analysis of Algorithms 235 Divide and Conquer 236 Dynamic Programming 237 Greedy Algorithms 242 Sorting and Selection 246 NP-Completeness 263