Introduction xxix
Chapter 1 Algorithm Basics 1
Approach 2
Algorithms and Data Structures 2
Pseudocode 3
Algorithm Features 6
Big O Notation 7
Rule 1 8
Rule 2 8
Rule 3 9
Rule 4 9
Rule 5 10
Common Run Time Functions 11
1 11
Log N 11
Sqrt N 14
N 14
N log N 15
N2 15
2N 15
N! 16
Visualizing Functions 16
Practical Considerations 18
Summary 19
Exercises 20
Chapter 2 Numerical Algorithms 23
Randomizing Data 23
Generating Random Values 23
Generating Values 24
Ensuring Fairness 26
Getting Fairness from Biased Sources 28
Randomizing Arrays 29
Generating Nonuniform Distributions 30
Making Random Walks 31
Making Self-Avoiding Walks 33
Making Complete Self-Avoiding Walks 34
Finding Greatest Common Divisors 36
Calculating Greatest Common Divisors 36
Extending Greatest Common Divisors 38
Performing Exponentiation 40
Working with Prime Numbers 42
Finding Prime Factors 42
Finding Primes 44
Testing for Primality 45
Performing Numerical Integration 47
The Rectangle Rule 48
The Trapezoid Rule 49
Adaptive Quadrature 50
Monte Carlo Integration 54
Finding Zeros 55
Gaussian Elimination 57
Forward Elimination 58
Back Substitution 60
The Algorithm 61
Least Squares Fits 62
Linear Least Squares 62
Polynomial Least Squares 64
Summary 67
Exercises 68
Chapter 3 Linked Lists 71
Basic Concepts 71
Singly Linked Lists 72
Iterating Over the List 73
Finding Cells 73
Using Sentinels 74
Adding Cells at the Beginning 75
Adding Cells at the End 76
Inserting Cells After Other Cells 77
Deleting Cells 78
Doubly Linked Lists 79
Sorted Linked Lists 81
Self-Organizing Linked Lists 82
Move to Front (MTF) 83
Swap 83
Count 84
Hybrid Methods 84
Pseudocode 85
Linked-List Algorithms 86
Copying Lists 86
Sorting with Insertionsort 87
Sorting with Selectionsort 88
Multithreaded Linked Lists 90
Linked Lists with Loops 91
Marking Cells 92
Using Hash Tables 93
List Retracing 94
List Reversal 95
Tortoise and Hare 98
Loops in Doubly Linked Lists 100
Summary 100
Exercises 101
Chapter 4 Arrays 103
Basic Concepts 103
One-Dimensional Arrays 106
Finding Items 106
Finding Minimum, Maximum, and Average 107
Finding Median 108
Finding Mode 109
Inserting Items 112
Removing Items 113
Nonzero Lower Bounds 114
Two Dimensions 114
Higher Dimensions 115
Triangular Arrays 118
Sparse Arrays 121
Find a Row or Column 123
Get a Value 124
Set a Value 125
Delete a Value 127
Matrices 129
Summary 131
Exercises 132
Chapter 5 Stacks and Queues 135
Stacks 135
Linked-List Stacks 136
Array Stacks 138
Double Stacks 139
Stack Algorithms 141
Reversing an Array 141
Train Sorting 142
Tower of Hanoi 143
Stack Insertionsort 145
Stack Selectionsort 146
Queues 147
Linked-List Queues 148
Array Queues 148
Specialized Queues 151
Priority Queues 151
Deques 152
Binomial Heaps 152
Binomial Trees 152
Binomial Heaps 154
Merging Trees 155
Merging Heaps 156
Merging Tree Lists 156
Merging Trees 158
Enqueue 161
Dequeue 162
Runtime 163
Summary 163
Exercises 164
Chapter 6 Sorting 167
O(N2 ) Algorithms 168
Insertionsort in Arrays 168
Selectionsort in Arrays 170
Bubblesort 171
O(NlogN) Algorithms 174
Heapsort 175
Storing Complete Binary Trees 175
Defining Heaps 176
Implementing Heapsort 180
Quicksort 181
Analyzing Quicksort’s Run Time 182
Picking a Dividing Item 184
Implementing Quicksort with Stacks 185
Implementing Quicksort in Place 185
Using Quicksort 188
Mergesort 189
Sub O(NlogN) Algorithms 192
Countingsort 192
Pigeonhole Sort 193
Bucketsort 195
Summary 197
Exercises 198
Chapter 7 Searching 201
Linear Search 202
Binary Search 203
Interpolation Search 204
Majority Voting 205
Summary 207
Exercises 208
Chapter 8 Hash Tables 209
Hash Table Fundamentals 210
Chaining 211
Open Addressing 213
Removing Items 214
Linear Probing 215
Quadratic Probing 217
Pseudorandom Probing 219
Double Hashing 219
Ordered Hashing 219
Summary 222
Exercises 222
Chapter 9 Recursion 227
Basic Algorithms 228
Factorial 228
Fibonacci Numbers 230
Rod-Cutting 232
Brute Force 233
Recursion 233
Tower of Hanoi 235
Graphical Algorithms 238
Koch Curves 239
Hilbert Curve 241
Sierpi?ski Curve 243
Gaskets 246
The Skyline Problem 247
Lists 248
Divide and Conquer 249
Backtracking Algorithms 252
Eight Queens Problem 254
Knight’s Tour 257
Selections and Permutations 260
Selections with Loops 261
Selections with Duplicates 262
Selections without Duplicates 264
Permutations with Duplicates 265
Permutations without Duplicates 266
Round-Robin Scheduling 267
Odd Number of Teams 268
Even Number of Teams 270
Implementation 271
Recursion Removal 273
Tail Recursion Removal 274
Dynamic Programming 275
Bottom-Up Programming 277
General Recursion Removal 277
Summary 280
Exercises 281
Chapter 10 Trees 285
Tree Terminology 285
Binary Tree Properties 289
Tree Representations 292
Building Trees in General 292
Building Complete Trees 295
Tree Traversal 296
Preorder Traversal 297
Inorder Traversal 299
Postorder Traversal 300
Breadth-First Traversal 301
Traversal Uses 302
Traversal Run Times 303
Sorted Trees 303
Adding Nodes 303
Finding Nodes 306
Deleting Nodes 306
Lowest Common Ancestors 309
Sorted Trees 309
Parent Pointers 310
Parents and Depths 311
General Trees 312
Euler Tours 314
All Pairs 316
Threaded Trees 317
Building Threaded Trees 318
Using Threaded Trees 320
Specialized Tree Algorithms 322
The Animal Game 322
Expression Evaluation 324
Interval Trees 326
Building the Tree 328
Intersecting with Points 329
Intersecting with Intervals 330
Quadtrees 332
Adding Items 335
Finding Items 336
Tries 337
Adding Items 339
Finding Items 341
Summary 342
Exercises 342
Chapter 11 Balanced Trees 349
AVL Trees 350
Adding Values 350
Deleting Values 353
2-3 Trees 354
Adding Values 355
Deleting Values 356
B-Trees 359
Adding Values 360
Deleting Values 361
Balanced Tree Variations 362
Top-down B-trees 363
B+trees 363
Summary 365
Exercises 365
Chapter 12 Decision Trees 367
Searching Game Trees 368
Minimax 369
Initial Moves and Responses 373
Game Tree Heuristics 374
Searching General Decision Trees 375
Optimization Problems 376
Exhaustive Search 377
Branch and Bound 379
Decision Tree Heuristics 381
Random Search 381
Improving Paths 382
Simulated Annealing 384
Hill Climbing 385
Sorted Hill Climbing 386
Other Decision Tree Problems 387
Generalized Partition Problem 387
Subset Sum 388
Bin Packing 388
Cutting Stock 389
Knapsack 390
Traveling Salesman Problem 391
Satisfiability 391
Swarm Intelligence 392
Ant Colony Optimization 393
General Optimization 393
Traveling Salesman 393
Bees Algorithm 394
Swarm Simulation 394
Boids 395
Pseudoclassical Mechanics 396
Goals and Obstacles 397
Summary 397
Exercises 398
Chapter 13 Basic Network Algorithms 403
Network Terminology 403
Network Representations 407
Traversals 409
Depth-First Traversal 410
Breadth-First Traversal 412
Connectivity Testing 413
Spanning Trees 416
Minimal Spanning Trees 417
Euclidean Minimum Spanning Trees 418
Building Mazes 419
Strongly Connected Components 420
Kosaraju’s Algorithm 421
Algorithm Discussion 422
Finding Paths 425
Finding Any Path 425
Label-Setting Shortest Paths 426
Label-Correcting Shortest Paths 430
All-Pairs Shortest Paths 431
Transitivity 436
Transitive Closure 437
Transitive Reduction 438
Acyclic Networks 439
General Networks 440
Shortest Path Modifications 441
Shape Points 441
Early Stopping 442
Bidirectional Search 442
Best-First Search 442
Turn Penalties and Prohibitions 443
Geometric Calculations 443
Expanded Node Networks 444
Interchange Networks 445
Summary 447
Exercises 447
Chapter 14 More Network Algorithms 451
Topological Sorting 451
Cycle Detection 455
Map Coloring 456
Two-Coloring 456
Three-Coloring 458
Four-Coloring 459
Five-Coloring 459
Other Map-Coloring Algorithms 462
Maximal Flow 464
Work Assignment 467
Minimal Flow Cut 468
Network Cloning 470
Dictionaries 471
Clone References 472
Cliques 473
Brute Force 474
Bron–Kerbosch 475
Sets R, P, and X 475
Recursive Calls 476
Pseudocode 476
Example 477
Variations 480
Finding Triangles 480
Brute Force 481
Checking Local Links 481
Chiba and Nishizeki 482
Community Detection 483
Maximal Cliques 483
Girvan–Newman 483
Clique Percolation 485
Eulerian Paths and Cycles 485
Brute Force 486
Fleury’s Algorithm 486
Hierholzer’s Algorithm 487
Summary 488
Exercises 489
Chapter 15 String Algorithms 493
Matching Parentheses 494
Evaluating Arithmetic Expressions 495
Building Parse Trees 496
Pattern Matching 497
DFAs 497
Building DFAs for Regular Expressions 500
NFAs 502
String Searching 504
Calculating Edit Distance 508
Phonetic Algorithms 511
Soundex 511
Metaphone 513
Summary 514
Exercises 515
Chapter 16 Cryptography 519
Terminology 520
Transposition Ciphers 521
Row/Column Transposition 521
Column Transposition 523
Route Ciphers 525
Substitution Ciphers 526
Caesar Substitution 526
Vigenere Cipher 527
Simple Substitution 529
One-Time Pads 530
Block Ciphers 531
Substitution-Permutation Networks 531
Feistel Ciphers 533
Public-Key Encryption and RSA 534
Euler’s Totient Function 535
Multiplicative Inverses 536
An RSA Example 536
Practical Considerations 537
Other Uses for Cryptography 538
Summary 539
Exercises 540
Chapter 17 Complexity Theory 543
Notation 544
Complexity Classes 545
Reductions 548
3SAT 549
Bipartite Matching 550
NP-Hardness 550
Detection, Reporting, and Optimization Problems 551
Detection ≤p Reporting 552
Reporting ≤p Optimization 552
Reporting ≤p Detection 552
Optimization ≤p Reporting 553
Approximate Optimization 553
NP-Complete Problems 554
Summary 557
Exercises 558
Chapter 18 Distributed Algorithms 561
Types of Parallelism 562
Systolic Arrays 562
Distributed Computing 565
Multi-CPU Processing 567
Race Conditions 567
Deadlock 571
Quantum Computing 572
Distributed Algorithms 573
Debugging Distributed Algorithms 573
Embarrassingly Parallel Algorithms 574
Mergesort 576
Dining Philosophers 577
Randomization 578
Resource Hierarchy 578
Waiter 579
Chandy/Misra 579
The Two Generals Problem 580
Byzantine Generals 581
Consensus 584
Leader Election 587
Snapshot 588
Clock Synchronization 589
Summary 591
Exercises 591
Chapter 19 Interview Puzzles 595
Asking Interview Puzzle Questions 597
Answering Interview Puzzle Questions 598
Summary 602
Exercises 604
Appendix A Summary of Algorithmic Concepts 607
Chapter 1: Algorithm Basics 607
Chapter 2: Numeric Algorithms 608
Chapter 3: Linked Lists 609
Chapter 4: Arrays 610
Chapter 5: Stacks and Queues 610
Chapter 6: Sorting 610
Chapter 7: Searching 611
Chapter 8: Hash Tables 612
Chapter 9: Recursion 612
Chapter 10: Trees 614
Chapter 11: Balanced Trees 615
Chapter 12: Decision Trees 615
Chapter 13: Basic Network Algorithms 616
Chapter 14: More Network Algorithms 617
Chapter 15: String Algorithms 618
Chapter 16: Cryptography 618
Chapter 17: Complexity Theory 619
Chapter 18: Distributed Algorithms 620
Chapter 19: Interview Puzzles 621
Appendix B Solutions to Exercises 623
Chapter 1: Algorithm Basics 623
Chapter 2: Numerical Algorithms 626
Chapter 3: Linked Lists 633
Chapter 4: Arrays 638
Chapter 5: Stacks and Queues 648
Chapter 6: Sorting 650
Chapter 7: Searching 653
Chapter 8: Hash Tables 655
Chapter 9: Recursion 658
Chapter 10: Trees 663
Chapter 11: Balanced Trees 670
Chapter 12: Decision Trees 675
Chapter 13: Basic Network Algorithms 678
Chapter 14: More Network Algorithms 681
Chapter 15: String Algorithms 686
Chapter 16: Encryption 689
Chapter 17: Complexity Theory 692
Chapter 18: Distributed Algorithms 697
Chapter 19: Interview Puzzles 701
Glossary 711
Index 739
