Algorithms

Prerequisites......Page 5
 Additional References......Page 7
 About the Exercises......Page 8
 Steal This Book!......Page 9
 Acknowledgments......Page 10
 Caveat Lector!......Page 11
Table of Contents......Page 13
 What is an algorithm?......Page 19
  Lattice Multiplication......Page 21
  Duplation and Mediation......Page 23
  Compass and Straightedge......Page 25
 Congressional Apportionment......Page 26
 A Bad Example......Page 28
 Describing Algorithms......Page 29
  Specifying the Problem......Page 30
  Describing the Algorithm......Page 31
  Correctness......Page 32
  Running Time......Page 33
 Exercises......Page 35
 Reductions......Page 39
 Simplify and Delegate......Page 40
 Tower of Hanoi......Page 42
 Mergesort......Page 44
  Correctness......Page 45
  Analysis......Page 46
  Correctness......Page 47
  Analysis......Page 48
 Recursion Trees......Page 49
  ♥Ignoring Floors and Ceilings Is Okay, Honest......Page 52
  Quickselect......Page 53
  Good pivots......Page 54
  Analysis......Page 55
  Sanity Checking......Page 57
 Fast Multiplication......Page 58
 Exponentiation......Page 60
 Exercises......Page 62
 N Queens......Page 89
 Game Trees......Page 91
 Subset Sum......Page 94
  Analysis......Page 95
  Variants......Page 96
 The General Pattern......Page 97
 Text Segmentation (Interpunctio Verborum)......Page 98
  Index Formulation......Page 101
  ♥Analysis......Page 102
  Variants......Page 103
 Longest Increasing Subsequence......Page 104
 Longest Increasing Subsequence, Take 2......Page 107
 Optimal Binary Search Trees......Page 109
  ♥Analysis......Page 110
 Exercises......Page 111
 Mātrāvṛtta......Page 115
  Backtracking Can Be Slow......Page 116
  Memo(r)ization: Remember Everything......Page 117
  Dynamic Programming: Fill Deliberately......Page 119
  Don\'t Remember Everything After All......Page 120
 ♥Aside: Even Faster Fibonacci Numbers......Page 121
  Whoa! Not so fast!......Page 122
 The Pattern: Smart Recursion......Page 123
 Warning: Greed is Stupid......Page 125
  First Recurrence: Is This Next?......Page 127
  Second Recurrence: What\'s Next?......Page 128
 Edit Distance......Page 129
  Recurrence......Page 130
  Dynamic Programming......Page 131
 Subset Sum......Page 134
 Optimal Binary Search Trees......Page 135
 Dynamic Programming on Trees......Page 138
 Exercises......Page 141
 Storing Files on Tape......Page 177
 Scheduling Classes......Page 179
 General Pattern......Page 182
 Huffman Codes......Page 183
 Stable Matching......Page 187
  Some Bad Ideas......Page 189
  The Boston Pool and Gale-Shapley Algorithms......Page 190
  Correctness......Page 192
  Optimality!......Page 193
 Exercises......Page 194
 Introduction and History......Page 205
 Basic Definitions......Page 208
 Representations and Examples......Page 210
  Adjacency Lists......Page 213
  Adjacency Matrices......Page 214
  Comparison......Page 216
 Whatever-First Search......Page 217
  Stack: Depth-First......Page 219
  Priority Queue: Best-First......Page 220
  Disconnected Graphs......Page 221
 Graph Reductions: Flood Fill......Page 223
 Exercises......Page 225
Depth-First Search......Page 243
 Preorder and Postorder......Page 245
  Classifying Vertices and Edges......Page 246
 Detecting Cycles......Page 249
  Implicit Topological Sort......Page 250
 Memoization and Dynamic Programming......Page 252
  Dynamic Programming in Dags......Page 253
 Strong Connectivity......Page 255
 Strong Components in Linear Time......Page 256
  Kosaraju and Sharir’s Algorithm......Page 258
  ♥Tarjan’s Algorithm......Page 260
 Exercises......Page 262
 Distinct Edge Weights......Page 275
 The Only Minimum Spanning Tree Algorithm......Page 277
 Borůvka’s Algorithm......Page 279
  This is the MST Algorithm You Want......Page 280
 Jarník’s (“Prim’s”) Algorithm......Page 281
  ♥Improving Jarník’s Algorithm......Page 282
 Kruskal’s Algorithm......Page 283
 Exercises......Page 286
Shortest Paths......Page 291
 ♥Negative Edges......Page 292
 The Only SSSP Algorithm......Page 294
 Unweighted Graphs: Breadth-First Search......Page 296
 Directed Acyclic Graphs: Depth-First Search......Page 300
 Best-First: Dijkstra’s Algorithm......Page 302
  No Negative Edges......Page 304
  ♥Negative Edges......Page 306
 Relax ALL the Edges: Bellman-Ford......Page 307
  Moore’s Improvement......Page 310
  Dynamic Programming Formulation......Page 312
 Exercises......Page 315
 Introduction......Page 327
 Lots of Single Sources......Page 328
 Reweighting......Page 329
 Johnson\'s Algorithm......Page 330
 Dynamic Programming......Page 331
 Divide and Conquer......Page 333
 Funny Matrix Multiplication......Page 334
 (Kleene-Roy-)Floyd-Warshall(-Ingerman)......Page 336
 Exercises......Page 338
Maximum Flows & Minimum Cuts......Page 345
 Flows......Page 346
 Cuts......Page 347
 The Maxflow-Mincut Theorem......Page 349
 Ford and Fulkerson\'s augmenting-path algorithm......Page 352
  ♥Irrational Capacities......Page 353
 Combining and Decomposing Flows......Page 354
  Fattest Augmenting Paths......Page 358
  Shortest Augmenting Paths......Page 359
 Further Progress......Page 361
 Exercises......Page 362
 Edge-Disjoint Paths......Page 371
 Vertex Capacities and Vertex-Disjoint Paths......Page 372
 Bipartite Matching......Page 373
 Tuple Selection......Page 374
  Exam Scheduling......Page 376
 Disjoint-Path Covers......Page 378
  Minimal Faculty Hiring......Page 380
 Baseball Elimination......Page 381
 Project Selection......Page 384
 Exercises......Page 386
 A Game You Can\'t Win......Page 397
 P versus NP......Page 399
 NP-hard, NP-easy, and NP-complete......Page 400
 ♥Formal Definitions (HC SVNT DRACONES)......Page 402
 Reductions and Sat......Page 403
 3Sat (from CircuitSat)......Page 406
 Maximum Independent Set (from 3Sat)......Page 408
 The General Pattern......Page 410
 Graph Coloring (from 3Sat)......Page 412
  From Vertex Cover......Page 416
  From 3Sat......Page 418
  Variants and Extensions......Page 419
 Subset Sum (from Vertex Cover)......Page 420
 Other Useful NP-hard Problems......Page 422
 Choosing the Right Problem......Page 425
 A Frivolous Real-World Example......Page 426
 ♥On Beyond Zebra......Page 429
  Polynomial Space......Page 430
  Exponential Time......Page 431
  Excelsior!......Page 432
 Exercises......Page 433
Index......Page 447
Index of People......Page 461
Index of Pseudocode......Page 465
Image Credits......Page 469
Colophon......Page 471