Algorithm Design Manual (eBook)

Steven Skiena is Professor of Computer Science at Stony Brook University. His research interests include the design of graph, string, and geometric algorithms, and their applications (particularly to biology). He is the author of four books, including "The Algorithm Design Manual" and "Calculated Bets: Computers, Gambling, and Mathematical Modeling to Win". He is recipient of the ONR Young Investigator Award and the IEEE Computer Science and Engineering Undergraduate Teaching Award.

Preface 5
Contents 10
I Practical Algorithm Design 16
Introduction to Algorithm Design 17
Robot Tour Optimization 19
Selecting the Right Jobs 23
Reasoning about Correctness 25
Modeling the Problem 33
About the War Stories 36
War Story: Psychic Modeling 37
Exercises 41
Algorithm Analysis 45
The RAM Model of Computation 45
The Big Oh Notation 48
Growth Rates and Dominance Relations 51
Working with the Big Oh 54
Reasoning About Efficiency 55
Logarithms and Their Applications 60
Properties of Logarithms 64
War Story: Mystery of the Pyramids 65
Advanced Analysis (*) 68
Exercises 71
Data Structures 79
Contiguous vs. Linked Data Structures 80
Stacks and Queues 85
Dictionaries 86
Binary Search Trees 91
Priority Queues 97
War Story: Stripping Triangulations 99
Hashing and Strings 103
Specialized Data Structures 107
War Story: String 'em Up 108
Exercises 112
Sorting and Searching 117
Applications of Sorting 118
Pragmatics of Sorting 121
Heapsort: Fast Sorting via Data Structures 122
War Story: Give me a Ticket on an Airplane 132
Mergesort: Sorting by Divide-and-Conquer 134
Quicksort: Sorting by Randomization 137
Distribution Sort: Sorting via Bucketing 143
War Story: Skiena for the Defense 145
Binary Search and Related Algorithms 146
Divide-and-Conquer 149
Exercises 153
Graph Traversal 159
Flavors of Graphs 160
Data Structures for Graphs 165
War Story: I was a Victim of Moore's Law 169
War Story: Getting the Graph 172
Traversing a Graph 175
Breadth-First Search 176
Applications of Breadth-First Search 180
Depth-First Search 183
Applications of Depth-First Search 186
Depth-First Search on Directed Graphs 192
Exercises 198
Weighted Graph Algorithms 205
Minimum Spanning Trees 206
War Story: Nothing but Nets 216
Shortest Paths 219
War Story: Dialing for Documents 226
Network Flows and Bipartite Matching 231
Design Graphs, Not Algorithms 236
Exercises 239
Combinatorial Search and Heuristic Methods 244
Backtracking 245
Search Pruning 252
Sudoku 253
War Story: Covering Chessboards 258
Heuristic Search Methods 261
War Story: Only it is Not a Radio 274
War Story: Annealing Arrays 277
Other Heuristic Search Methods 280
Parallel Algorithms 281
War Story: Going Nowhere Fast 282
Exercises 284
Dynamic Programming 287
Caching vs. Computation 288
Approximate String Matching 294
Longest Increasing Sequence 303
War Story: Evolution of the Lobster 305
The Partition Problem 308
Parsing Context-Free Grammars 312
Limitations of Dynamic Programming: TSP 315
War Story: What's Past is Prolog 318
War Story: Text Compression for Bar Codes 321
Exercises 324
Intractable Problems and Approximation Algorithms 330
Problems and Reductions 331
Reductions for Algorithms 333
Elementary Hardness Reductions 337
Satisfiability 342
Creative Reductions 344
The Art of Proving Hardness 348
War Story: Hard Against the Clock 351
War Story: And Then I Failed 353
P vs. NP 355
Dealing with NP-complete Problems 358
Exercises 364
How to Design Algorithms 370
II The Hitchhiker's Guide to Algorithms 375
A Catalog of Algorithmic Problems 376
Data Structures 379
Dictionaries 380
Priority Queues 386
Suffix Trees and Arrays 390
Graph Data Structures 394
Set Data Structures 398
Kd-Trees 402
Numerical Problems 406
Solving Linear Equations 408
Bandwidth Reduction 411
Matrix Multiplication 414
Determinants and Permanents 417
Constrained and Unconstrained Optimization 420
Linear Programming 424
Random Number Generation 428
Factoring and Primality Testing 433
Arbitrary-Precision Arithmetic 436
Knapsack Problem 440
Discrete Fourier Transform 444
Combinatorial Problems 447
Sorting 449
Searching 454
Median and Selection 458
Generating Permutations 461
Generating Subsets 465
Generating Partitions 469
Generating Graphs 473
Calendrical Calculations 478
Job Scheduling 481
Satisfiability 485
Graph Problems: Polynomial-Time 488
Connected Components 490
Topological Sorting 494
Minimum Spanning Tree 497
Shortest Path 502
Transitive Closure and Reduction 508
Matching 511
Eulerian Cycle/Chinese Postman 515
Edge and Vertex Connectivity 518
Network Flow 522
Drawing Graphs Nicely 526
Drawing Trees 530
Planarity Detection and Embedding 533
Graph Problems: Hard Problems 536
Clique 538
Independent Set 541
Vertex Cover 543
Traveling Salesman Problem 546
Hamiltonian Cycle 551
Graph Partition 554
Vertex Coloring 557
Edge Coloring 561
Graph Isomorphism 563
Steiner Tree 568
Feedback Edge/Vertex Set 572
Computational Geometry 575
Robust Geometric Primitives 577
Convex Hull 581
Triangulation 585
Voronoi Diagrams 589
Nearest Neighbor Search 593
Range Search 597
Point Location 600
Intersection Detection 604
Bin Packing 608
Medial-Axis Transform 611
Polygon Partitioning 614
Simplifying Polygons 617
Shape Similarity 620
Motion Planning 623
Maintaining Line Arrangements 627
Minkowski Sum 630
Set and String Problems 633
Set Cover 634
Set Packing 638
String Matching 641
Approximate String Matching 644
Text Compression 650
Cryptography 654
Finite State Machine Minimization 659
Longest Common Substring/Subsequence 663
Shortest Common Superstring 667
Algorithmic Resources 670
Software Systems 670
Data Sources 676
Online Bibliographic Resources 676
Professional Consulting Services 677
Bibliography 678
Index 721