|
I Practical Algorithm Design |
|
|
1 | (360) |
|
1 Introduction to Algorithm Design |
|
|
3 | (28) |
|
1.1 Robot Tour Optimization |
|
|
5 | (4) |
|
1.2 Selecting the Right Jobs |
|
|
9 | (2) |
|
1.3 Reasoning about Correctness |
|
|
11 | (8) |
|
|
19 | (3) |
|
1.5 About the War Stories |
|
|
22 | (1) |
|
1.6 War Story: Psychic Modeling |
|
|
23 | (4) |
|
|
27 | (4) |
|
|
31 | (34) |
|
2.1 The RAM Model of Computation |
|
|
31 | (3) |
|
|
34 | (3) |
|
2.3 Growth Rates and Dominance Relations |
|
|
37 | (3) |
|
2.4 Working with the Big Oh |
|
|
40 | (1) |
|
2.5 Reasoning About Efficiency |
|
|
41 | (5) |
|
2.6 Logarithms and Their Applications |
|
|
46 | (4) |
|
2.7 Properties of Logarithms |
|
|
50 | (1) |
|
2.8 War Story: Mystery of the Pyramids |
|
|
51 | (3) |
|
2.9 Advanced Analysis (*) |
|
|
54 | (3) |
|
|
57 | (8) |
|
|
65 | (38) |
|
3.1 Contiguous vs. Linked Data Structures |
|
|
66 | (5) |
|
|
71 | (1) |
|
|
72 | (5) |
|
|
77 | (6) |
|
|
83 | (2) |
|
3.6 War Story: Stripping Triangulations |
|
|
85 | (4) |
|
|
89 | (4) |
|
3.8 Specialized Data Structures |
|
|
93 | (1) |
|
3.9 War Story: String 'em Up |
|
|
94 | (4) |
|
|
98 | (5) |
|
|
103 | (42) |
|
4.1 Applications of Sorting |
|
|
104 | (3) |
|
4.2 Pragmatics of Sorting |
|
|
107 | (1) |
|
4.3 Heapsort: Fast Sorting via Data Structures |
|
|
108 | (10) |
|
4.4 War Story: Give me a Ticket on an Airplane |
|
|
118 | (2) |
|
4.5 Mergesort: Sorting by Divide-and-Conquer |
|
|
120 | (3) |
|
4.6 Quicksort: Sorting by Randomization |
|
|
123 | (6) |
|
4.7 Distribution Sort: Sorting via Bucketing |
|
|
129 | (2) |
|
4.8 War Story: Skiena for the Defense |
|
|
131 | (1) |
|
4.9 Binary Search and Related Algorithms |
|
|
132 | (3) |
|
|
135 | (4) |
|
|
139 | (6) |
|
|
145 | (46) |
|
|
146 | (5) |
|
5.2 Data Structures for Graphs |
|
|
151 | (4) |
|
5.3 War Story: I was a Victim of Moore's Law |
|
|
155 | (3) |
|
5.4 War Story: Getting the Graph |
|
|
158 | (3) |
|
|
161 | (1) |
|
|
162 | (4) |
|
5.7 Applications of Breadth-First Search |
|
|
166 | (3) |
|
|
169 | (3) |
|
5.9 Applications of Depth-First Search |
|
|
172 | (6) |
|
5.10 Depth-First Search on Directed Graphs |
|
|
178 | (6) |
|
|
184 | (7) |
|
6 Weighted Graph Algorithms |
|
|
191 | (39) |
|
6.1 Minimum Spanning Trees |
|
|
192 | (10) |
|
6.2 War Story: Nothing but Nets |
|
|
202 | (3) |
|
|
205 | (7) |
|
6.4 War Story: Dialing for Documents |
|
|
212 | (5) |
|
6.5 Network Flows and Bipartite Matching |
|
|
217 | (5) |
|
6.6 Design Graphs, Not Algorithms |
|
|
222 | (3) |
|
|
225 | (5) |
|
7 Combinatorial Search and Heuristic Methods |
|
|
230 | (43) |
|
|
231 | (7) |
|
|
238 | (1) |
|
|
239 | (5) |
|
7.4 War Story: Covering Chessboards |
|
|
244 | (3) |
|
7.5 Heuristic Search Methods |
|
|
247 | (13) |
|
7.6 War Story: Only it is Not a Radio |
|
|
260 | (3) |
|
7.7 War Story: Annealing Arrays |
|
|
263 | (3) |
|
7.8 Other Heuristic Search Methods |
|
|
266 | (1) |
|
|
267 | (1) |
|
7.10 War Story: Going Nowhere Fast |
|
|
268 | (2) |
|
|
270 | (3) |
|
|
273 | (43) |
|
8.1 Caching vs. Computation |
|
|
274 | (6) |
|
8.2 Approximate String Matching |
|
|
280 | (9) |
|
8.3 Longest Increasing Sequence |
|
|
289 | (2) |
|
8.4 War Story: Evolution of the Lobster |
|
|
291 | (3) |
|
8.5 The Partition Problem |
|
|
294 | (4) |
|
8.6 Parsing Context-Free Grammars |
|
|
298 | (3) |
|
8.7 Limitations of Dynamic Programming: TSP |
|
|
301 | (3) |
|
8.8 War Story: What's Past is Prolog |
|
|
304 | (3) |
|
8.9 War Story: Text Compression for Bar Codes |
|
|
307 | (3) |
|
|
310 | (6) |
|
9 Intractable Problems and Approximation Algorithms |
|
|
316 | (40) |
|
9.1 Problems and Reductions |
|
|
317 | (2) |
|
9.2 Reductions for Algorithms |
|
|
319 | (4) |
|
9.3 Elementary Hardness Reductions |
|
|
323 | (5) |
|
|
328 | (2) |
|
|
330 | (4) |
|
9.6 The Art of Proving Hardness |
|
|
334 | (3) |
|
9.7 War Story: Hard Against the Clock |
|
|
337 | (2) |
|
9.8 War Story: And Then I Failed |
|
|
339 | (2) |
|
|
341 | (3) |
|
9.10 Dealing with NP-complete Problems |
|
|
344 | (6) |
|
|
350 | (6) |
|
10 How to Design Algorithms |
|
|
356 | (5) |
|
II The Hitchhiker's Guide to Algorithms |
|
|
361 | (304) |
|
11 A Catalog of Algorithmic Problems |
|
|
363 | (3) |
|
|
366 | (27) |
|
|
367 | (6) |
|
|
373 | (4) |
|
12.3 Suffix Trees and Arrays |
|
|
377 | (4) |
|
12.4 Graph Data Structures |
|
|
381 | (4) |
|
|
385 | (4) |
|
|
389 | (4) |
|
|
393 | (41) |
|
13.1 Solving Linear Equations |
|
|
395 | (3) |
|
|
398 | (3) |
|
13.3 Matrix Multiplication |
|
|
401 | (3) |
|
13.4 Determinants and Permanents |
|
|
404 | (3) |
|
13.5 Constrained and Unconstrained Optimization |
|
|
407 | (4) |
|
|
411 | (4) |
|
13.7 Random Number Generation |
|
|
415 | (5) |
|
13.8 Factoring and Primality Testing |
|
|
420 | (3) |
|
13.9 Arbitrary-Precision Arithmetic |
|
|
423 | (4) |
|
|
427 | (4) |
|
13.11 Discrete Fourier Transform |
|
|
431 | (3) |
|
14 Combinatorial Problems |
|
|
434 | (41) |
|
|
436 | (5) |
|
|
441 | (4) |
|
14.3 Median and Selection |
|
|
445 | (3) |
|
14.4 Generating Permutations |
|
|
448 | (4) |
|
|
452 | (4) |
|
14.6 Generating Partitions |
|
|
456 | (4) |
|
|
460 | (5) |
|
14.8 Calendrical Calculations |
|
|
465 | (3) |
|
|
468 | (4) |
|
|
472 | (3) |
|
15 Graph Problems: Polynomial-Time |
|
|
475 | (48) |
|
15.1 Connected Components |
|
|
477 | (4) |
|
|
481 | (3) |
|
15.3 Minimum Spanning Tree |
|
|
484 | (5) |
|
|
489 | (6) |
|
15.5 Transitive Closure and Reduction |
|
|
495 | (3) |
|
|
498 | (4) |
|
15.7 Eulerian Cycle/Chinese Postman |
|
|
502 | (3) |
|
15.8 Edge and Vertex Connectivity |
|
|
505 | (4) |
|
|
509 | (4) |
|
15.10 Drawing Graphs Nicely |
|
|
513 | (4) |
|
|
517 | (3) |
|
15.12 Planarity Detection and Embedding |
|
|
520 | (3) |
|
16 Graph Problems: Hard Problems |
|
|
523 | (39) |
|
|
525 | (3) |
|
|
528 | (2) |
|
|
530 | (3) |
|
16.4 Traveling Salesman Problem |
|
|
533 | (5) |
|
|
538 | (3) |
|
|
541 | (3) |
|
|
544 | (4) |
|
|
548 | (2) |
|
|
550 | (5) |
|
|
555 | (4) |
|
16.11 Feedback Edge/Vertex Set |
|
|
559 | (3) |
|
17 Computational Geometry |
|
|
562 | (58) |
|
17.1 Robust Geometric Primitives |
|
|
564 | (4) |
|
|
568 | (4) |
|
|
572 | (4) |
|
|
576 | (4) |
|
17.5 Nearest Neighbor Search |
|
|
580 | (4) |
|
|
584 | (3) |
|
|
587 | (4) |
|
17.8 Intersection Detection |
|
|
591 | (4) |
|
|
595 | (3) |
|
17.10 Medial-Axis Transform |
|
|
598 | (3) |
|
17.11 Polygon Partitioning |
|
|
601 | (3) |
|
17.12 Simplifying Polygons |
|
|
604 | (3) |
|
|
607 | (3) |
|
|
610 | (4) |
|
17.15 Maintaining Line Arrangements |
|
|
614 | (3) |
|
|
617 | (3) |
|
18 Set and String Problems |
|
|
620 | (37) |
|
|
621 | (4) |
|
|
625 | (3) |
|
|
628 | (3) |
|
18.4 Approximate String Matching |
|
|
631 | (6) |
|
|
637 | (4) |
|
|
641 | (5) |
|
18.7 Finite State Machine Minimization |
|
|
646 | (4) |
|
18.8 Longest Common Substring/Subsequence |
|
|
650 | (4) |
|
18.9 Shortest Common Superstring |
|
|
654 | (3) |
|
|
657 | (8) |
|
|
657 | (6) |
|
|
663 | (1) |
|
19.3 Online Bibliographic Resources |
|
|
663 | (1) |
|
19.4 Professional Consulting Services |
|
|
664 | (1) |
Bibliography |
|
665 | (44) |
Index |
|
709 | |