Essential Algorithms

Cover......Page 1
Title Page......Page 5
Copyright......Page 6
About the Author......Page 9
About the Technical Editor......Page 11
Credits......Page 13
Acknowledgments......Page 15
Contents at a glance......Page 17
Contents......Page 19
Introduction......Page 31
 Algorithm Selection......Page 33
 Who This Book Is For......Page 34
 This Book’s Websites......Page 35
 How This Book Is Structured......Page 36
 What You Need to Use This Book......Page 38
 Conventions......Page 39
 How to Contact the Author......Page 40
Chapter 1 Algorithm Basics......Page 41
 Algorithms and Data Structures......Page 42
 Pseudocode......Page 43
 Algorithm Features......Page 46
  Big O Notation......Page 47
   Rule 2......Page 48
   Rule 4......Page 49
   Rule 5......Page 50
   Log N......Page 51
   N......Page 54
   2N......Page 55
  Visualizing Functions......Page 56
 Practical Considerations......Page 58
 Summary......Page 59
 Exercises......Page 60
  Generating Random Values......Page 63
   Generating Values......Page 64
   Ensuring Fairness......Page 66
   Getting Fairness from Biased Sources......Page 68
  Randomizing Arrays......Page 69
  Generating Nonuniform Distributions......Page 70
  Making Random Walks......Page 71
   Making Self-Avoiding Walks......Page 73
   Making Complete Self-Avoiding Walks......Page 74
  Calculating Greatest Common Divisors......Page 76
  Extending Greatest Common Divisors......Page 78
 Performing Exponentiation......Page 80
  Finding Prime Factors......Page 82
  Finding Primes......Page 84
  Testing for Primality......Page 85
 Performing Numerical Integration......Page 87
  The Rectangle Rule......Page 88
  The Trapezoid Rule......Page 89
  Adaptive Quadrature......Page 90
  Monte Carlo Integration......Page 94
 Finding Zeros......Page 95
 Gaussian Elimination......Page 97
  Forward Elimination......Page 98
  Back Substitution......Page 100
  The Algorithm......Page 101
  Linear Least Squares......Page 102
  Polynomial Least Squares......Page 104
 Summary......Page 107
 Exercises......Page 108
 Basic Concepts......Page 111
 Singly Linked Lists......Page 112
  Finding Cells......Page 113
  Using Sentinels......Page 114
  Adding Cells at the Beginning......Page 115
  Adding Cells at the End......Page 116
  Inserting Cells After Other Cells......Page 117
  Deleting Cells......Page 118
 Doubly Linked Lists......Page 119
 Sorted Linked Lists......Page 121
 Self-Organizing Linked Lists......Page 122
  Swap......Page 123
  Hybrid Methods......Page 124
  Pseudocode......Page 125
  Copying Lists......Page 126
  Sorting with Insertionsort......Page 127
  Sorting with Selectionsort......Page 128
 Multithreaded Linked Lists......Page 130
 Linked Lists with Loops......Page 131
  Marking Cells......Page 132
  Using Hash Tables......Page 133
  List Retracing......Page 134
  List Reversal......Page 135
  Tortoise and Hare......Page 138
 Summary......Page 140
 Exercises......Page 141
 Basic Concepts......Page 143
  Finding Items......Page 146
  Finding Minimum, Maximum, and Average......Page 147
  Finding Median......Page 148
  Finding Mode......Page 149
  Inserting Items......Page 152
  Removing Items......Page 153
  Two Dimensions......Page 154
  Higher Dimensions......Page 155
 Triangular Arrays......Page 158
 Sparse Arrays......Page 161
  Find a Row or Column......Page 163
  Get a Value......Page 164
  Set a Value......Page 165
  Delete a Value......Page 167
 Matrices......Page 169
 Summary......Page 171
 Exercises......Page 172
 Stacks......Page 175
  Linked-List Stacks......Page 176
  Array Stacks......Page 178
  Double Stacks......Page 179
   Reversing an Array......Page 181
   Train Sorting......Page 182
   Tower of Hanoi......Page 183
   Stack Insertionsort......Page 185
   Stack Selectionsort......Page 186
 Queues......Page 187
  Array Queues......Page 188
   Priority Queues......Page 191
  Binomial Trees......Page 192
  Binomial Heaps......Page 194
  Merging Trees......Page 195
   Merging Tree Lists......Page 196
   Merging Trees......Page 198
  Enqueue......Page 201
  Dequeue......Page 202
 Summary......Page 203
 Exercises......Page 204
Chapter 6 Sorting......Page 207
  Insertionsort in Arrays......Page 208
  Selectionsort in Arrays......Page 210
  Bubblesort......Page 211
 O(NlogN) Algorithms......Page 214
   Storing Complete Binary Trees......Page 215
   Defining Heaps......Page 216
   Implementing Heapsort......Page 220
  Quicksort......Page 221
   Analyzing Quicksort’s Run Time......Page 222
   Picking a Dividing Item......Page 224
   Implementing Quicksort in Place......Page 225
   Using Quicksort......Page 228
  Mergesort......Page 229
  Countingsort......Page 232
  Pigeonhole Sort......Page 233
  Bucketsort......Page 235
 Summary......Page 237
 Exercises......Page 238
Chapter 7 Searching......Page 241
 Linear Search......Page 242
 Binary Search......Page 243
 Interpolation Search......Page 244
 Majority Voting......Page 245
 Summary......Page 247
 Exercises......Page 248
Chapter 8 Hash Tables......Page 249
 Hash Table Fundamentals......Page 250
 Chaining......Page 251
 Open Addressing......Page 253
  Removing Items......Page 254
  Linear Probing......Page 255
  Quadratic Probing......Page 257
  Ordered Hashing......Page 259
 Exercises......Page 262
Chapter 9 Recursion......Page 267
  Factorial......Page 268
  Fibonacci Numbers......Page 270
  Rod-Cutting......Page 272
   Recursion......Page 273
  Tower of Hanoi......Page 275
 Graphical Algorithms......Page 278
  Koch Curves......Page 279
  Hilbert Curve......Page 281
  Sierpiski Curve......Page 283
  Gaskets......Page 286
  The Skyline Problem......Page 287
   Lists......Page 288
   Divide and Conquer......Page 289
 Backtracking Algorithms......Page 292
  Eight Queens Problem......Page 294
  Knight’s Tour......Page 297
 Selections and Permutations......Page 300
  Selections with Loops......Page 301
  Selections with Duplicates......Page 302
  Selections Without Duplicates......Page 304
  Permutations with Duplicates......Page 305
  Permutations Without Duplicates......Page 306
  Round-Robin Scheduling......Page 307
   Odd Number of Teams......Page 308
   Even Number of Teams......Page 310
   Implementation......Page 311
 Recursion Removal......Page 313
  Tail Recursion Removal......Page 314
  Dynamic Programming......Page 315
  General Recursion Removal......Page 317
 Summary......Page 320
 Exercises......Page 321
 Tree Terminology......Page 325
 Binary Tree Properties......Page 329
  Building Trees in General......Page 332
  Building Complete Trees......Page 335
 Tree Traversal......Page 336
  Preorder Traversal......Page 337
  Inorder Traversal......Page 339
  Postorder Traversal......Page 340
  Breadth-First Traversal......Page 341
  Traversal Uses......Page 342
  Adding Nodes......Page 343
  Deleting Nodes......Page 346
  Sorted Trees......Page 349
  Parent Pointers......Page 350
  Parents and Depths......Page 351
  General Trees......Page 352
  Euler Tours......Page 354
  All Pairs......Page 356
 Threaded Trees......Page 357
  Building Threaded Trees......Page 358
  Using Threaded Trees......Page 360
  The Animal Game......Page 362
  Expression Evaluation......Page 364
 Interval Trees......Page 366
  Building the Tree......Page 368
  Intersecting with Points......Page 369
  Intersecting with Intervals......Page 370
  Quadtrees......Page 372
   Adding Items......Page 375
   Finding Items......Page 376
  Tries......Page 377
   Adding Items......Page 379
   Finding Items......Page 381
 Exercises......Page 382
Chapter 11 Balanced Trees......Page 389
  Adding Values......Page 390
  Deleting Values......Page 393
 2-3 Trees......Page 394
  Adding Values......Page 395
  Deleting Values......Page 396
 B-Trees......Page 399
  Adding Values......Page 400
  Deleting Values......Page 401
 Balanced Tree Variations......Page 402
  B+trees......Page 403
 Exercises......Page 405
Chapter 12 Decision Trees......Page 407
 Searching Game Trees......Page 408
  Minimax......Page 409
  Initial Moves and Responses......Page 413
  Game Tree Heuristics......Page 414
 Searching General Decision Trees......Page 415
  Optimization Problems......Page 416
  Exhaustive Search......Page 417
  Branch and Bound......Page 419
   Random Search......Page 421
   Improving Paths......Page 422
   Simulated Annealing......Page 424
   Hill Climbing......Page 425
   Sorted Hill Climbing......Page 426
   Generalized Partition Problem......Page 427
   Bin Packing......Page 428
   Cutting Stock......Page 429
   Knapsack......Page 430
   Satisfiability......Page 431
 Swarm Intelligence......Page 432
   Traveling Salesman......Page 433
  Swarm Simulation......Page 434
   Boids......Page 435
   Pseudoclassical Mechanics......Page 436
 Summary......Page 437
 Exercises......Page 438
 Network Terminology......Page 443
 Network Representations......Page 447
 Traversals......Page 449
  Depth-First Traversal......Page 450
  Breadth-First Traversal......Page 452
  Connectivity Testing......Page 453
  Spanning Trees......Page 456
  Minimal Spanning Trees......Page 457
  Euclidean Minimum Spanning Trees......Page 458
  Building Mazes......Page 459
 Strongly Connected Components......Page 460
  Kosaraju’s Algorithm......Page 461
  Algorithm Discussion......Page 462
  Finding Any Path......Page 465
  Label-Setting Shortest Paths......Page 466
  Label-Correcting Shortest Paths......Page 470
  All-Pairs Shortest Paths......Page 471
 Transitivity......Page 476
  Transitive Closure......Page 477
  Transitive Reduction......Page 478
   Acyclic Networks......Page 479
   General Networks......Page 480
  Shape Points......Page 481
  Best-First Search......Page 482
   Geometric Calculations......Page 483
   Expanded Node Networks......Page 484
   Interchange Networks......Page 485
 Exercises......Page 487
 Topological Sorting......Page 491
 Cycle Detection......Page 495
  Two-Coloring......Page 496
  Three-Coloring......Page 498
  Five-Coloring......Page 499
  Other Map-Coloring Algorithms......Page 502
 Maximal Flow......Page 504
  Work Assignment......Page 507
  Minimal Flow Cut......Page 508
 Network Cloning......Page 510
  Dictionaries......Page 511
  Clone References......Page 512
 Cliques......Page 513
  Brute Force......Page 514
   Sets R, P, and X......Page 515
   Pseudocode......Page 516
   Example......Page 517
  Finding Triangles......Page 520
   Checking Local Links......Page 521
   Chiba and Nishizeki......Page 522
  Girvan–Newman......Page 523
 Eulerian Paths and Cycles......Page 525
  Fleury’s Algorithm......Page 526
  Hierholzer’s Algorithm......Page 527
 Summary......Page 528
 Exercises......Page 529
Chapter 15 String Algorithms......Page 533
 Matching Parentheses......Page 534
  Evaluating Arithmetic Expressions......Page 535
  Building Parse Trees......Page 536
  DFAs......Page 537
  Building DFAs for Regular Expressions......Page 540
  NFAs......Page 542
 String Searching......Page 544
 Calculating Edit Distance......Page 548
  Soundex......Page 551
  Metaphone......Page 553
 Summary......Page 554
 Exercises......Page 555
Chapter 16 Cryptography......Page 559
 Terminology......Page 560
  Row/Column Transposition......Page 561
  Column Transposition......Page 563
  Route Ciphers......Page 565
  Caesar Substitution......Page 566
  Vigenère Cipher......Page 567
  Simple Substitution......Page 569
  One-Time Pads......Page 570
  Substitution-Permutation Networks......Page 571
  Feistel Ciphers......Page 573
 Public-Key Encryption and RSA......Page 574
  Euler’s Totient Function......Page 575
  An RSA Example......Page 576
  Practical Considerations......Page 577
 Other Uses for Cryptography......Page 578
 Summary......Page 579
 Exercises......Page 580
Chapter 17 Complexity Theory......Page 583
 Notation......Page 584
 Complexity Classes......Page 585
 Reductions......Page 588
  3SAT......Page 589
 NP-Hardness......Page 590
 Detection, Reporting, and Optimization Problems......Page 591
  Reporting ≤p Detection......Page 592
  Approximate Optimization......Page 593
 NP-Complete Problems......Page 594
 Summary......Page 597
 Exercises......Page 598
Chapter 18 Distributed Algorithms......Page 601
  Systolic Arrays......Page 602
  Distributed Computing......Page 605
  Race Conditions......Page 607
  Deadlock......Page 611
  Quantum Computing......Page 612
  Debugging Distributed Algorithms......Page 613
  Embarrassingly Parallel Algorithms......Page 614
  Mergesort......Page 616
  Dining Philosophers......Page 617
   Resource Hierarchy......Page 618
   Chandy/Misra......Page 619
  The Two Generals Problem......Page 620
  Byzantine Generals......Page 621
  Consensus......Page 624
  Leader Election......Page 627
  Snapshot......Page 628
  Clock Synchronization......Page 629
 Exercises......Page 631
Chapter 19 Interview Puzzles......Page 635
 Asking Interview Puzzle Questions......Page 637
 Answering Interview Puzzle Questions......Page 638
 Summary......Page 642
 Exercises......Page 644
 Chapter 1: Algorithm Basics......Page 647
 Chapter 2: Numeric Algorithms......Page 648
 Chapter 3: Linked Lists......Page 649
 Chapter 6: Sorting......Page 650
 Chapter 7: Searching......Page 651
 Chapter 9: Recursion......Page 652
 Chapter 10: Trees......Page 654
 Chapter 12: Decision Trees......Page 655
 Chapter 13: Basic Network Algorithms......Page 656
 Chapter 14: More Network Algorithms......Page 657
 Chapter 16: Cryptography......Page 658
 Chapter 17: Complexity Theory......Page 659
 Chapter 18: Distributed Algorithms......Page 660
 Chapter 19: Interview Puzzles......Page 661
 Chapter 1: Algorithm Basics......Page 663
 Chapter 2: Numerical Algorithms......Page 666
 Chapter 3: Linked Lists......Page 673
 Chapter 4: Arrays......Page 678
 Chapter 5: Stacks and Queues......Page 688
 Chapter 6: Sorting......Page 690
 Chapter 7: Searching......Page 693
 Chapter 8: Hash Tables......Page 695
 Chapter 9: Recursion......Page 698
 Chapter 10: Trees......Page 703
 Chapter 11: Balanced Trees......Page 710
 Chapter 12: Decision Trees......Page 715
 Chapter 13: Basic Network Algorithms......Page 718
 Chapter 14: More Network Algorithms......Page 721
 Chapter 15: String Algorithms......Page 726
 Chapter 16: Encryption......Page 729
 Chapter 17: Complexity Theory......Page 732
 Chapter 18: Distributed Algorithms......Page 737
 Chapter 19: Interview Puzzles......Page 741
Glossary......Page 751
Index......Page 779
EULA......Page 803