Essential Algorithms: A Practical Approach to Computer Algorithms Using Python and C#

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 N² 15 2^N 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(N² ) 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 SierpiDski 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