Essential Algorithms

Rod Stephens began his career as a mathematician, but while at MIT he was lured into the intriguing world of algorithms and has been programming ever since. An award-winning instructor, he regularly addresses conferences and has written 26 books that have been translated into nearly a dozen languages.

Introduction xv Chapter 1 Algorithm Basics 1 Approach 2 Algorithms and Data Structures 3 Pseudocode 3 Algorithm Features 6 Big O Notation 7 Common Runtime Functions 11 Visualizing Functions 17 Practical Considerations 17 Summary 19 Exercises 20 Chapter 2 Numerical Algorithms 25 Randomizing Data 25 Generating Random Values 25 Randomizing Arrays 31 Generating Nonuniform Distributions 33 Finding Greatest Common Divisors 33 Performing Exponentiation 35 Working with Prime Numbers 36 Finding Prime Factors 37 Finding Primes 39 Testing for Primality 40 Performing Numerical Integration 42 The Rectangle Rule 42 The Trapezoid Rule 43 Adaptive Quadrature 44 Monte Carlo Integration 48 Finding Zeros 49 Summary 51 Exercises 52 Chapter 3 Linked Lists 55 Basic Concepts 55 Singly Linked Lists 56 Iterating Over the List 57 Finding Cells 57 Using Sentinels 58 Adding Cells at the Beginning 59 Adding Cells at the End 60 Inserting Cells After Other Cells 61 Deleting Cells 62 Doubly Linked Lists 63 Sorted Linked Lists 65 Linked-List Algorithms 66 Copying Lists 67 Sorting with Insertionsort 68 Linked List Selectionsort 69 Multithreaded Linked Lists 70 Linked Lists with Loops 71 Marking Cells 72 Using Hash Tables 74 List Retracing 75 List Reversal 76 Tortoise and Hare 78 Loops in Doubly Linked Lists 80 Summary 81 Exercises 81 Chapter 4 Arrays 83 Basic Concepts 83 One-dimensional Arrays 86 Finding Items 86 Finding Minimum, Maximum, and Average 86 Inserting Items 88 Removing Items 89 Nonzero Lower Bounds 89 Two Dimensions 90 Higher Dimensions 91 Triangular Arrays 94 Sparse Arrays 97 Find a Row or Column 100 Get a Value 101 Set a Value 101 Delete a Value 104 Matrices 105 Summary 108 Exercises 108 Chapter 5 Stacks and Queues 111 Stacks 111 Linked-List Stacks 112 Array Stacks 113 Double Stacks 115 Stack Algorithms 117 Queues 123 Linked-List Queues 123 Array Queues 124 Specialized Queues 127 Summary 128 Exercises 128 Chapter 6 Sorting 131 O(N2) Algorithms 132 Insertionsort in Arrays 132 Selectionsort in Arrays 134 Bubblesort 135 O(N log N) Algorithms 138 Heapsort 139 Quicksort 145 Mergesort 153 Sub O(N log N) Algorithms 156 Countingsort 156 Bucketsort 157 Summary 159 Exercises 160 Chapter 7 Searching 163 Linear Search 164 Binary Search 165 Interpolation Search 166 Summary 167 Exercises 168 Chapter 8 Hash Tables 169 Hash Table Fundamentals 170 Chaining 171 Open Addressing 172 Removing Items 174 Liner Probing 174 Quadratic Probing 176 Pseudorandom Probing 178 Double Hashing 178 Ordered Hashing 179 Summary 181 Exercises 182 Chapter 9 Recursion 185 Basic Algorithms 186 Factorial 186 Fibonacci Numbers 188 Tower of Hanoi 189 Graphical Algorithms 193 Koch Curves 193 Hilbert Curve 196 Sierpin' ski Curve 197 Gaskets 200 Backtracking Algorithms 201 Eight Queens Problem 203 Knight s Tour 206 Selections and Permutations 209 Selections with Loops 210 Selections with Duplicates 211 Selections Without Duplicates 213 Permutations with Duplicates 214 Permutations Without Duplicates 215 Recursion Removal 216 Tail Recursion Removal 216 Storing Intermediate Values 218 General Recursion Removal 220 Summary 222 Exercises 223 Chapter 10 Trees 227 Tree Terminology 227 Binary Tree Properties 231 Tree Representations 234 Building Trees in General 234 Building Complete Trees 236 Tree Traversal 237 Preorder Traversal 238 Inorder Traversal 240 Postorder Traversal 242 Depth-first Traversal 243 Traversal Run Times 244 Sorted Trees 245 Adding Nodes 245 Finding Nodes 247 Deleting Nodes 248 Threaded Trees 250 Building Threaded Trees 251 Using Threaded Trees 254 Specialized Tree Algorithms 256 The Animal Game 256 Expression Evaluation 258 Quadtrees 260 Tries 266 Summary 270 Exercises 271 Chapter 11 Balanced Trees 277 AVL Trees 278 Adding Values 278 Deleting Values 281 2-3 Trees 282 Adding Values 283 Deleting Values 284 B-Trees 287 Adding Values 288 Deleting Values 289 Balanced Tree Variations 291 Top-down B-trees 291 B+trees 291 Summary 293 Exercises 293 Chapter 12 Decision Trees 297 Searching Game Trees 298 Minimax 298 Initial Moves and Responses 302 Game Tree Heuristics 303 Searching General Decision Trees 305 Optimization Problems 306 Exhaustive Search 307 Branch and Bound 309 Decision Tree Heuristics 310 Other Decision Tree Problems 316 Summary 322 Exercises 322 Chapter 13 Basic Network Algorithms 325 Network Terminology 325 Network Representations 328 Traversals 331 Depth-first Traversal 331 Breadth-first Traversal 334 Connectivity Testing 335 Spanning Trees 337 Minimal Spanning Trees 338 Finding Paths 339 Finding Any Path 339 Label-Setting Shortest Paths 340 Label-Correcting Shortest Paths 344 All-Pairs Shortest Paths 345 Summary 350 Exercises 351 Chapter 14 More Network Algorithms 355 Topological Sorting 355 Cycle Detection 359 Map Coloring 359 Two-coloring 360 Three-coloring 362 Four-coloring 362 Five-coloring 363 Other Map-coloring Algorithms 367 Maximal Flow 368 Work Assignment 370 Minimal Flow Cut 372 Summary 374 Exercises 375 Chapter 15 String Algorithms 377 Matching Parentheses 378 Evaluating Arithmetic Expressions 379 Building Parse Trees 380 Pattern Matching 381 DFAs 381 Building DFAs for Regular Expressions 383 NFAs 386 String Searching 387 Calculating Edit Distance 391 Summary 394 Exercises 394 Chapter 16 Cryptography 397 Terminology 398 Transposition Ciphers 399 Row/column Transposition 399 Column Transposition 401 Route Ciphers 403 Substitution Ciphers 404 Caesar Substitution 404 Vigenere Cipher 405 Simple Substitution 407 One-Time Pads 408 Block Ciphers 408 Substitution-Permutation Networks 409 Feistel Ciphers 410 Public-Key Encryption and RSA 412 Euler s Totient Function 413 Multiplicative Inverses 413 An RSA Example 414 Practical Considerations 414 Other Uses for Cryptography 415 Summary 416 Exercises 417 Chapter 17 Complexity Theory 419 Notation 420 Complexity Classes 421 Reductions 424 3SAT 425 Bipartite Matching 426 NP-Hardness 426 Detection, Reporting, and Optimization Problems 427 Detection p Reporting 427 Reporting p Optimization 428 Reporting p Detection 428 Optimization p Reporting 429 NP-Complete Problems 429 Summary 431 Exercises 432 Chapter 18 Distributed Algorithms 435 Types of Parallelism 436 Systolic Arrays 436 Distributed Computing 438 Multi-CPU Processing 440 Race Conditions 440 Deadlock 444 Quantum Computing 445 Distributed Algorithms 446 Debugging Distributed Algorithms 446 Embarrassingly Parallel Algorithms 447 Mergesort 449 Dining Philosophers 449 The Two Generals Problem 452 Byzantine Generals 453 Consensus 455 Leader Election 458 Snapshot 459 Clock Synchronization 460 Summary 462 Exercises 462 Chapter 19 Interview Puzzles 465 Asking Interview Puzzle Questions 467 Answering Interview Puzzle Questions 468 Summary 472 Exercises 474 Appendix A Summary of Algorithmic Concepts 477 Appendix B Solutions to Exercises 487 Glossary 559 Index 573