Ⅰ Practical Algorithm Design 1
1 Introduction to Algorithm Design 3
1.1 Robot Tour Optimization 5
1.2 Selecting the Right Jobs 9
1.3 Reasoning about Correctness 11
1.4 Modeling the Problem 19
1.5 About the War Stories 22
1.6 War Story: Psychic Modeling 23
1.7 Exercises 27
2 Algorithm Analysis 31
2.1 The RAM Model of Computation 31
2.2 The Big Oh Notation 34
2.3 Growth Rates and Dominance Relations 37
2.4 Working with the Big Oh 40
2.5 Reasoning About Efficiency 41
2.6 Logarithms and Their Applications 46
2.7 Properties of Logarithms 50
2.8 War Story: Mystery of the Pyramids 51
2.9 Advanced Analysis（*） 54
2.10 Exercises 57
3 Data Structures 65
3.1 Contiguous vs.Linked Data Structures 66
3.2 Stacks and Queues 71
3.3 Dictionaries 72
3.4 Binary Search Trees 77
3.5 Priority Queues 83
3.6 War Story: Stripping Triangulations 85
3.7 Hashing and Strings 89
3.8 Specialized Data Structures 93
3.9 War Story: String ’em Up 94
3.10 Exercises 98
4 Sorting and Searching 103
4.1 Applications of Sorting 104
4.2 Pragmatics of Sorting 107
4.3 Heapsort: Fast Sorting via Data Structures 108
4.4 War Story: Give me a Ticket on an Airplane 118
4.5 Mergesort: Sorting by Divide-and-Conquer 120
4.6 Quicksort: Sorting by Randomization 123
4.7 Distribution Sort: Sorting via Bucketing 129
4.8 War Story: Skiena for the Defense 131
4.9 Binary Search and Related Algorithms 132
4.10 Divide-and-Conquer 135
4.11 Exercises 139
5 Graph Traversal 145
5.1 Flavors of Graphs 146
5.2 Data Structures for Graphs 151
5.3 War Story: I was a Victim of Moore’s Law 155
5.4 War Story: Getting the Graph 158
5.5 Traversing a Graph 161
5.6 Breadth-First Search 162
5.7 Applications of Breadth-First Search 166
5.8 Depth-First Search 169
5.9 Applications of Depth-First Search 172
5.10 Depth-First Search on Directed Graphs 178
5.11 Exercises 184
6 Weighted Graph Algorithms 191
6.1 Minimum Spanning Trees 192
6.2 War Story: Nothing but Nets 202
6.3 Shortest Paths 205
6.4 War Story: Dialing for Documents 212
6.5 Network Flows and Bipartite Matching 217
6.6 Design Graphs, Not Algorithms 222
6.7 Exercises 225
7 Combinatorial Search and Heuristic Methods 230
7.1 Backtracking 231
7.2 Search Pruning 238
7.3 Sudoku 239
7.4 War Story: Covering Chessboards 244
7.5 Heuristic Search Methods 247
7.6 War Story: Only it is Not a Radio 260
7.7 War Story: Annealing Arrays 263
7.8 Other Heuristic Search Methods 266
7.9 Parallel Algorithms 267
7.10 War Story: Going Nowhere Fast 268
7.11 Exercises 270
8 Dynamic Programming 273
8.1 Caching vs.Computation 274
8.2 Approximate String Matching 280
8.3 Longest Increasing Sequence 289
8.4 War Story: Evolution of the Lobster 291
8.5 The Partition Problem 294
8.6 Parsing Context-Free Grammars 298
8.7 Limitations of Dynamic Programming: TSP 301
8.8 War Story: What’s Past is Prolog 304
8.9 War Story: Text Compression for Bar Codes 307
8.10 Exercises 310
9 Intractable Problems and Approximation Algorithms 316
9.1 Problems and Reductions 317
9.2 Reductions for Algorithms 319
9.3 Elementary Hardness Reductions 323
9.4 Satistiability 328
9.5 Creative Reductions 330
9.6 The Art of Proving Hardness 334
9.7 War Story: Hard Against the Clock 337
9.8 War Story: And Then I Failed 339
9.9 P vs.NP 341
9.10 Dealing with NP-complete Problems 344
9.11 Exercises 350
10 How to Design Algorithms 356
Ⅱ The Hitchhiker’s Guide to Algorithms 361
11 A Catalog of Algorithmic Problems 363
12 Data Structures 366
12.1 Dictionaries 367
12.2 Priority Queues 373
12.3 Suffix Trees and Arrays 377
12.4 Graph Data Structures 381
12.5 Set Data Structures 385
12.6 Kd-Trees 389
13 Numerical Problems 393
13.1 Solving Linear Equations 395
13.2 Bandwidth Reduction 398
13.3 Matrix Multiplication 401
13.4 Determinants and Permanents 404
13.5 Constrained and Unconstrained Optimization 407
13.6 Linear Programming 411
13.7 Random Number Generation 415
13.8 Factoring and Primality Testing 420
13.9 Arbitrary-Precision Arithmetic 423
13.10 Knapsack Problem 427
13.11 Discrete Fourier Transform 431
14 Combinatorial Problems 434
14.1 Sorting 436
14.2 Searching 441
14.3 Median and Selection 445
14.4 Generating Permutations 448
14.5 Generating Subsets 452
14.6 Generating Partitions 456
14.7 Generating Graphs 460
14.8 Calendrical Calculations 465
14.9 Job Scheduling 468
14.10 Satisfiability 472
15 Graph Problems: Polynomial-Time 475
15.1 Connected Components 477
15.2 Topological Sorting 481
15.3 Minimum Spanning Tree 484
15.4 Shortest Path 489
15.5 Transitive Closure and Reduction 495
15.6 Matching 498
15.7 Eulerian Cycle/Chinese Postman 502
15.8 Edge and Vertex Connectivity 505
15.9 Network Flow 509
15.10 Drawing Graphs Nicely 513
15.11 Drawing Trees 517
15.12 Planarity Detection and Embedding 520
16 Graph Problems: Hard Problems 523
16.1 Clique 525
16.2 Independent Set 528
16.3 Vertex Cover 530
16.4 Traveling Salesman Problem 533
16.5 Hamiltonian Cycle 538
16.6 Graph Partition 541
16.7 Vertex Coloring 544
16.8 Edge Coloring 548
16.9 Graph Isomorphism 550
16.10 Steiner Tree 555
16.11 Feedback Edge/Vertex Set 559
17 Computational Geometry 562
17.1 Robust Geometric Primitives 564
17.2 Convex Hull 568
17.3 Triangulation 572
17.4 Voronoi Diagrams 576
17.5 Nearest Neighbor Search 580
17.6 Range Search 584
17.7 Point Location 587
17.8 Intersection Detection 591
17.9 Bin Packing 595
17.10 Medial-Axis Transform 598
17.11 Polygon Partitioning 601
17.12 Simplifying Polygons 604
17.13 Shape Similarity 607
17.14 Motion Planning 610
17.15 Maintaining Line Arrangements 614
17.16 Minkowski Sum 617
18 Set and String Problems 620
18.1 Set Cover 621
18.2 Set Packing 625
18.3 String Matching 628
18.4 Approximate String Matching 631
18.5 Text Compression 637
18.6 Cryptography 641
18.7 Finite State Machine Minimization 646
18.8 Longest Common Substring/Subsequence 650
18.9 Shortest Common Superstring 654
19 Algorithmic Resources 657
19.1 Software Systems 657
19.2 Data Sources 663
19.3 Online Bibliographic Resources 663
19.4 Professional Consulting Services 664
Bibliography 665