I Practical Algorithm Design |
|
1 | (434) |
|
1 Introduction to Algorithm Design |
|
|
3 | (28) |
|
1.1 Robot Tour Optimization |
|
|
5 | (3) |
|
1.2 Selecting the Right Jobs |
|
|
8 | (3) |
|
1.3 Reasoning about Correctness |
|
|
11 | (4) |
|
1.3.1 Problems and Properties |
|
|
11 | (1) |
|
1.3.2 Expressing Algorithms |
|
|
12 | (1) |
|
1.3.3 Demonstrating Incorrectness |
|
|
13 | (2) |
|
1.4 Induction and Recursion |
|
|
15 | (2) |
|
|
17 | (4) |
|
1.5.1 Combinatorial Objects |
|
|
17 | (2) |
|
|
19 | (2) |
|
1.6 Proof by Contradiction |
|
|
21 | (1) |
|
1.7 About the War Stories |
|
|
22 | (1) |
|
1.8 War Story: Psychic Modeling |
|
|
22 | (3) |
|
|
25 | (2) |
|
|
27 | (4) |
|
|
31 | (38) |
|
2.1 The RAM Model of Computation |
|
|
31 | (3) |
|
2.1.1 Best-Case, Worst-Case, and Average-Case Complexity |
|
|
32 | (2) |
|
|
34 | (3) |
|
2.3 Growth Rates and Dominance Relations |
|
|
37 | (2) |
|
2.3.1 Dominance Relations |
|
|
38 | (1) |
|
2.4 Working with the Big Oh |
|
|
39 | (2) |
|
|
40 | (1) |
|
2.4.2 Multiplying Functions |
|
|
40 | (1) |
|
2.5 Reasoning about Efficiency |
|
|
41 | (5) |
|
|
41 | (1) |
|
|
42 | (1) |
|
2.5.3 String Pattern Matching |
|
|
43 | (2) |
|
2.5.4 Matrix Multiplication |
|
|
45 | (1) |
|
|
46 | (2) |
|
2.7 Logarithms and Their Applications |
|
|
48 | (4) |
|
2.7.1 Logarithms and Binary Search |
|
|
49 | (1) |
|
2.7.2 Logarithms and Trees |
|
|
49 | (1) |
|
2.7.3 Logarithms and Bits |
|
|
50 | (1) |
|
2.7.4 Logarithms and Multiplication |
|
|
50 | (1) |
|
2.7.5 Fast Exponentiation |
|
|
50 | (1) |
|
2.7.6 Logarithms and Summations |
|
|
51 | (1) |
|
2.7.7 Logarithms and Criminal Justice |
|
|
51 | (1) |
|
2.8 Properties of Logarithms |
|
|
52 | (2) |
|
2.9 War Story: Mystery of the Pyramids |
|
|
54 | (3) |
|
|
57 | (2) |
|
2.10.1 Esoteric Functions |
|
|
57 | (1) |
|
2.10.2 Limits and Dominance Relations |
|
|
58 | (1) |
|
|
59 | (10) |
|
|
69 | (40) |
|
3.1 Contiguous vs. Linked Data Structures |
|
|
69 | (6) |
|
|
70 | (1) |
|
3.1.2 Pointers and Linked Structures |
|
|
71 | (3) |
|
|
74 | (1) |
|
3.2 Containers: Stacks and Queues |
|
|
75 | (1) |
|
|
76 | (5) |
|
|
81 | (6) |
|
3.4.1 Implementing Binary Search Trees |
|
|
81 | (4) |
|
3.4.2 How Good are Binary Search Trees? |
|
|
85 | (1) |
|
3.4.3 Balanced Search Trees |
|
|
86 | (1) |
|
|
87 | (2) |
|
3.6 War Story: Stripping Triangulations |
|
|
89 | (4) |
|
|
93 | (5) |
|
3.7.1 Collision Resolution |
|
|
93 | (2) |
|
3.7.2 Duplicate Detection via Hashing |
|
|
95 | (1) |
|
3.7.3 Other Hashing Tricks |
|
|
96 | (1) |
|
|
96 | (1) |
|
|
97 | (1) |
|
3.8 Specialized Data Structures |
|
|
98 | (1) |
|
3.9 War Story: String 'em Up |
|
|
98 | (5) |
|
|
103 | (6) |
|
|
109 | (38) |
|
4.1 Applications of Sorting |
|
|
109 | (4) |
|
4.2 Pragmatics of Sorting |
|
|
113 | (2) |
|
4.3 Heapsort: Fast Sorting via Data Structures |
|
|
115 | (10) |
|
|
116 | (2) |
|
|
118 | (2) |
|
4.3.3 Extracting the Minimum |
|
|
120 | (2) |
|
4.3.4 Faster Heap Construction |
|
|
122 | (2) |
|
4.3.5 Sorting by Incremental Insertion |
|
|
124 | (1) |
|
4.4 War Story: Give me a Ticket on an Airplane |
|
|
125 | (2) |
|
4.5 Mergesort: Sorting by Divide and Conquer |
|
|
127 | (3) |
|
4.6 Quicksort: Sorting by Randomization |
|
|
130 | (6) |
|
4.6.1 Intuition: The Expected Case for Quicksort |
|
|
132 | (1) |
|
4.6.2 Randomized Algorithms |
|
|
133 | (2) |
|
4.6.3 Is Quicksort Really Quick? |
|
|
135 | (1) |
|
4.7 Distribution Sort: Sorting via Bucketing |
|
|
136 | (2) |
|
4.7.1 Lower Bounds for Sorting |
|
|
137 | (1) |
|
4.8 War Story: Skiena for the Defense |
|
|
138 | (2) |
|
|
140 | (7) |
|
|
147 | (24) |
|
5.1 Binary Search and Related Algorithms |
|
|
148 | (2) |
|
5.1.1 Counting Occurrences |
|
|
148 | (1) |
|
5.1.2 One-Sided Binary Search |
|
|
149 | (1) |
|
5.1.3 Square and Other Roots |
|
|
150 | (1) |
|
5.2 War Story: Finding the Bug in the Bug |
|
|
150 | (2) |
|
|
152 | (2) |
|
5.3.1 Divide-and-Conquer Recurrences |
|
|
153 | (1) |
|
5.4 Solving Divide-and-Conquer Recurrences |
|
|
154 | (1) |
|
|
155 | (2) |
|
5.6 Largest Subrange and Closest Pair |
|
|
157 | (2) |
|
|
159 | (2) |
|
|
159 | (1) |
|
5.7.2 Pitfalls of Parallelism |
|
|
160 | (1) |
|
5.8 War Story: Going Nowhere Fast |
|
|
161 | (1) |
|
|
162 | (4) |
|
5.9.1 Applications of Convolution |
|
|
163 | (1) |
|
5.9.2 Fast Polynomial Multiplication |
|
|
164 | (2) |
|
|
166 | (5) |
|
6 Hashing and Randomized Algorithms |
|
|
171 | (26) |
|
|
172 | (7) |
|
|
172 | (2) |
|
6.1.2 Compound Events and Independence |
|
|
174 | (1) |
|
6.1.3 Conditional Probability |
|
|
175 | (1) |
|
6.1.4 Probability Distributions |
|
|
176 | (1) |
|
|
176 | (1) |
|
|
177 | (2) |
|
6.2 Understanding Balls and Bins |
|
|
179 | (2) |
|
6.2.1 The Coupon Collector's Problem |
|
|
180 | (1) |
|
6.3 Why is Hashing a Randomized Algorithm? |
|
|
181 | (1) |
|
|
182 | (2) |
|
6.5 The Birthday Paradox and Perfect Hashing |
|
|
184 | (2) |
|
|
186 | (2) |
|
6.7 Efficient String Matching |
|
|
188 | (2) |
|
|
190 | (1) |
|
6.9 War Story: Giving Knuth the Middle Initial |
|
|
191 | (1) |
|
6.10 Where do Random Numbers Come From? |
|
|
192 | (1) |
|
|
193 | (4) |
|
|
197 | (46) |
|
|
198 | (5) |
|
7.1.1 The Friendship Graph |
|
|
201 | (2) |
|
7.2 Data Structures for Graphs |
|
|
203 | (4) |
|
7.3 War Story: I was a Victim of Moore's Law |
|
|
207 | (3) |
|
7.4 War Story: Getting the Graph |
|
|
210 | (2) |
|
|
212 | (1) |
|
|
213 | (4) |
|
7.6.1 Exploiting Traversal |
|
|
216 | (1) |
|
|
217 | (1) |
|
7.7 Applications of Breadth-First Search |
|
|
217 | (4) |
|
7.7.1 Connected Components |
|
|
218 | (1) |
|
7.7.2 Two-Coloring Graphs |
|
|
219 | (2) |
|
|
221 | (3) |
|
7.9 Applications of Depth-First Search |
|
|
224 | (6) |
|
|
224 | (1) |
|
7.9.2 Articulation Vertices |
|
|
225 | (5) |
|
7.10 Depth-First Search on Directed Graphs |
|
|
230 | (5) |
|
7.10.1 Topological Sorting |
|
|
231 | (1) |
|
7.10.2 Strongly Connected Components |
|
|
232 | (3) |
|
|
235 | (8) |
|
8 Weighted Graph Algorithms |
|
|
243 | (38) |
|
8.1 Minimum Spanning Trees |
|
|
244 | (10) |
|
|
245 | (3) |
|
8.1.2 Kruskal's Algorithm |
|
|
248 | (2) |
|
8.1.3 The Union-Find Data Structure |
|
|
250 | (3) |
|
8.1.4 Variations on Minimum Spanning Trees |
|
|
253 | (1) |
|
8.2 War Story: Nothing but Nets |
|
|
254 | (3) |
|
|
257 | (7) |
|
8.3.1 Dijkstra's Algorithm |
|
|
258 | (3) |
|
8.3.2 All-Pairs Shortest Path |
|
|
261 | (2) |
|
|
263 | (1) |
|
8.4 War Story: Dialing for Documents |
|
|
264 | (3) |
|
8.5 Network Flows and Bipartite Matching |
|
|
267 | (5) |
|
|
267 | (1) |
|
8.5.2 Computing Network Flows |
|
|
268 | (4) |
|
|
272 | (2) |
|
8.7 Design Graphs, Not Algorithms |
|
|
274 | (2) |
|
|
276 | (5) |
|
|
281 | (26) |
|
|
281 | (3) |
|
9.2 Examples of Backtracking |
|
|
284 | (5) |
|
9.2.1 Constructing All Subsets |
|
|
284 | (2) |
|
9.2.2 Constructing All Permutations |
|
|
286 | (1) |
|
9.2.3 Constructing All Paths in a Graph |
|
|
287 | (2) |
|
|
289 | (1) |
|
|
290 | (5) |
|
9.5 War Story: Covering Chessboards |
|
|
295 | (3) |
|
|
298 | (2) |
|
|
300 | (3) |
|
|
303 | (4) |
|
|
307 | (48) |
|
10.1 Caching vs. Computation |
|
|
308 | (6) |
|
10.1.1 Fibonacci Numbers by Recursion |
|
|
308 | (1) |
|
10.1.2 Fibonacci Numbers by Caching |
|
|
309 | (2) |
|
10.1.3 Fibonacci Numbers by Dynamic Programming |
|
|
311 | (1) |
|
10.1.4 Binomial Coefficients |
|
|
312 | (2) |
|
10.2 Approximate String Matching |
|
|
314 | (10) |
|
10.2.1 Edit Distance by Recursion |
|
|
315 | (2) |
|
10.2.2 Edit Distance by Dynamic Programming |
|
|
317 | (1) |
|
10.2.3 Reconstructing the Path |
|
|
318 | (3) |
|
10.2.4 Varieties of Edit Distance |
|
|
321 | (3) |
|
10.3 Longest Increasing Subsequence |
|
|
324 | (2) |
|
10.4 War Story: Text Compression for Bar Codes |
|
|
326 | (3) |
|
10.5 Unordered Partition or Subset Sum |
|
|
329 | (2) |
|
10.6 War Story: The Balance of Power |
|
|
331 | (2) |
|
10.7 The Ordered Partition Problem |
|
|
333 | (4) |
|
10.8 Parsing Context-Free Grammars |
|
|
337 | (2) |
|
10.9 Limitations of Dynamic Programming: TSP |
|
|
339 | (3) |
|
10.9.1 When is Dynamic Programming Correct? |
|
|
340 | (1) |
|
10.9.2 When is Dynamic Programming Efficient? |
|
|
341 | (1) |
|
10.10 War Story: What's Past is Prolog |
|
|
342 | (3) |
|
|
345 | (10) |
|
|
355 | (34) |
|
11.1 Problems and Reductions |
|
|
355 | (3) |
|
|
356 | (1) |
|
|
357 | (1) |
|
11.2 Reductions for Algorithms |
|
|
358 | (3) |
|
|
358 | (1) |
|
11.2.2 Longest Increasing Subsequence |
|
|
359 | (1) |
|
11.2.3 Least Common Multiple |
|
|
359 | (1) |
|
|
360 | (1) |
|
11.3 Elementary Hardness Reductions |
|
|
361 | (6) |
|
|
362 | (1) |
|
11.3.2 Independent Set and Vertex Cover |
|
|
363 | (3) |
|
|
366 | (1) |
|
|
367 | (2) |
|
|
367 | (2) |
|
11.5 Creative Reductions from SAT |
|
|
369 | (4) |
|
|
369 | (2) |
|
11.5.2 Integer Programming |
|
|
371 | (2) |
|
11.6 The Art of Proving Hardness |
|
|
373 | (2) |
|
11.7 War Story: Hard Against the Clock |
|
|
375 | (2) |
|
11.8 War Story: And Then I Failed |
|
|
377 | (2) |
|
|
379 | (4) |
|
11.9.1 Verification vs. Discovery |
|
|
380 | (1) |
|
11.9.2 The Classes P and NP |
|
|
380 | (1) |
|
11.9.3 Why Satisfiability is Hard |
|
|
381 | (1) |
|
11.9.4 NP-hard vs. NP-complete? |
|
|
382 | (1) |
|
|
383 | (6) |
|
12 Dealing with Hard Problems |
|
|
389 | (40) |
|
12.1 Approximation Algorithms |
|
|
389 | (1) |
|
12.2 Approximating Vertex Cover |
|
|
390 | (3) |
|
12.2.1 A Randomized Vertex Cover Heuristic |
|
|
392 | (1) |
|
|
393 | (3) |
|
12.3.1 The Christofides Heuristic |
|
|
394 | (2) |
|
12.4 When Average is Good Enough |
|
|
396 | (1) |
|
|
396 | (1) |
|
12.4.2 Maximum Acyclic Subgraph |
|
|
397 | (1) |
|
|
397 | (2) |
|
12.6 Heuristic Search Methods |
|
|
399 | (12) |
|
|
400 | (2) |
|
|
402 | (4) |
|
12.6.3 Simulated Annealing |
|
|
406 | (4) |
|
12.6.4 Applications of Simulated Annealing |
|
|
410 | (1) |
|
12.7 War Story: Only it is Not a Radio |
|
|
411 | (3) |
|
12.8 War Story: Annealing Arrays |
|
|
414 | (3) |
|
12.9 Genetic Algorithms and Other Heuristics |
|
|
417 | (1) |
|
|
418 | (8) |
|
12.10.1 Properties of "Quantum" Computers |
|
|
419 | (1) |
|
12.10.2 Grover's Algorithm for Database Search |
|
|
420 | (2) |
|
12.10.3 The Faster "Fourier Transform" |
|
|
422 | (1) |
|
12.10.4 Shor's Algorithm for Integer Factorization |
|
|
422 | (2) |
|
12.10.5 Prospects for Quantum Computing |
|
|
424 | (2) |
|
|
426 | (3) |
|
13 How to Design Algorithms |
|
|
429 | (6) |
|
13.1 Preparing for Tech Company Interviews |
|
|
433 | (2) |
II The Hitchhiker's Guide to Algorithms |
|
435 | (334) |
|
14 A Catalog of Algorithmic Problems |
|
|
437 | (2) |
|
|
439 | (26) |
|
|
440 | (5) |
|
|
445 | (3) |
|
15.3 Suffix Trees and Arrays |
|
|
448 | (4) |
|
15.4 Graph Data Structures |
|
|
452 | (4) |
|
|
456 | (4) |
|
|
460 | (5) |
|
|
465 | (40) |
|
16.1 Solving Linear Equations |
|
|
467 | (3) |
|
|
470 | (2) |
|
16.3 Matrix Multiplication |
|
|
472 | (3) |
|
16.4 Determinants and Permanents |
|
|
475 | (3) |
|
16.5 Constrained/Unconstrained Optimization |
|
|
478 | (4) |
|
|
482 | (4) |
|
16.7 Random Number Generation |
|
|
486 | (4) |
|
16.8 Factoring and Primality Testing |
|
|
490 | (3) |
|
16.9 Arbitrary-Precision Arithmetic |
|
|
493 | (4) |
|
|
497 | (4) |
|
16.11 Discrete Fourier Transform |
|
|
501 | (4) |
|
17 Combinatorial Problems |
|
|
505 | (36) |
|
|
506 | (4) |
|
|
510 | (4) |
|
17.3 Median and Selection |
|
|
514 | (3) |
|
17.4 Generating Permutations |
|
|
517 | (4) |
|
|
521 | (3) |
|
17.6 Generating Partitions |
|
|
524 | (4) |
|
|
528 | (4) |
|
17.8 Calendrical Calculations |
|
|
532 | (2) |
|
|
534 | (3) |
|
|
537 | (4) |
|
18 Graph Problems: Polynomial Time |
|
|
541 | (44) |
|
18.1 Connected Components |
|
|
542 | (4) |
|
|
546 | (3) |
|
18.3 Minimum Spanning Tree |
|
|
549 | (5) |
|
|
554 | (5) |
|
18.5 Transitive Closure and Reduction |
|
|
559 | (3) |
|
|
562 | (3) |
|
18.7 Eulerian Cycle/Chinese Postman |
|
|
565 | (3) |
|
18.8 Edge and Vertex Connectivity |
|
|
568 | (3) |
|
|
571 | (3) |
|
18.10 Drawing Graphs Nicely |
|
|
574 | (4) |
|
|
578 | (3) |
|
18.12 Planarity Detection and Embedding |
|
|
581 | (4) |
|
19 Graph Problems: NP-Hard |
|
|
585 | (36) |
|
|
586 | (3) |
|
|
589 | (2) |
|
|
591 | (3) |
|
19.4 Traveling Salesman Problem |
|
|
594 | (4) |
|
|
598 | (3) |
|
|
601 | (3) |
|
|
604 | (4) |
|
|
608 | (2) |
|
|
610 | (4) |
|
|
614 | (4) |
|
19.11 Feedback Edge/Vertex Set |
|
|
618 | (3) |
|
20 Computational Geometry |
|
|
621 | (56) |
|
20.1 Robust Geometric Primitives |
|
|
622 | (4) |
|
|
626 | (4) |
|
|
630 | (4) |
|
|
634 | (3) |
|
20.5 Nearest-Neighbor Search |
|
|
637 | (4) |
|
|
641 | (3) |
|
|
644 | (4) |
|
20.8 Intersection Detection |
|
|
648 | (4) |
|
|
652 | (3) |
|
20.10 Medial-Axis Transform |
|
|
655 | (3) |
|
20.11 Polygon Partitioning |
|
|
658 | (3) |
|
20.12 Simplifying Polygons |
|
|
661 | (3) |
|
|
664 | (3) |
|
|
667 | (4) |
|
20.15 Maintaining Line Arrangements |
|
|
671 | (3) |
|
|
674 | (3) |
|
21 Set and String Problems |
|
|
677 | (36) |
|
|
678 | (4) |
|
|
682 | (3) |
|
|
685 | (3) |
|
21.4 Approximate String Matching |
|
|
688 | (5) |
|
|
693 | (4) |
|
|
697 | (5) |
|
21.7 Finite State Machine Minimization |
|
|
702 | (4) |
|
21.8 Longest Common Substring/Subsequence |
|
|
706 | (3) |
|
21.9 Shortest Common Superstring |
|
|
709 | (4) |
|
|
713 | (6) |
|
|
713 | (4) |
|
|
713 | (1) |
|
|
714 | (1) |
|
22.1.3 Boost Graph Library |
|
|
714 | (1) |
|
|
714 | (1) |
|
22.1.5 Collected Algorithms of the ACM |
|
|
715 | (1) |
|
22.1.6 GitHub and SourceForge |
|
|
715 | (1) |
|
22.1.7 The Stanford GraphBase |
|
|
715 | (1) |
|
|
716 | (1) |
|
22.1.9 Programs from Books |
|
|
716 | (1) |
|
|
717 | (1) |
|
22.3 Online Bibliographic Resources |
|
|
718 | (1) |
|
22.4 Professional Consulting Services |
|
|
718 | (1) |
|
|
719 | (50) |
Index |
|
769 | |