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 more than 30 books that have been translated into nearly a dozen languages.

Select Guide Rating

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

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 more than 30 books that have been translated into nearly a dozen languages.

Select Guide Rating

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

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 more than 30 books that have been translated into nearly a dozen languages.

Select Guide Rating

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