| 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
|