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

A friendly introduction to the most useful algorithms written in simple, intuitive English The revised and updated second edition of Essential Algorithms, offers an accessible introduction to computer algorithms. The book contains a description of important classical algorithms and explains when each is appropriate. The author shows how to analyze algorithms in order to understand their behavior and teaches techniques that the can be used to create new algorithms to meet future needs. The text includes useful algorithms such as: methods for manipulating common data structures, advanced data structures, network algorithms, and numerical algorithms. It also offers a variety of general problem-solving techniques. In addition to describing algorithms and approaches, the author offers details on how to analyze the performance of algorithms. The book is filled with exercises that can be used to explore ways to modify the algorithms in order to apply them to new situations. This updated edition of Essential Algorithms : Contains explanations of algorithms in simple terms, rather than complicated math Steps through powerful algorithms that can be used to solve difficult programming problems Helps prepare for programming job interviews that typically include algorithmic questions Offers methods can be applied to any programming language Includes exercises and solutions useful to both professionals and students Provides code examples updated and written in Python and C# Essential Algorithms has been updated and revised and offers professionals and students a hands-on guide to analyzing algorithms as well as the techniques and applications. The book also includes a collection of questions that may appear in a job interview. The book's website will include reference implementations in Python and C# (which can be easily applied to Java and C++). 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

A friendly introduction to the most useful algorithms written in simple, intuitive English

The revised and updated second edition of Essential Algorithms, offers an accessible introduction to computer algorithms. The book contains a description of important classical algorithms and explains when each is appropriate. The author shows how to analyze algorithms in order to understand their behavior and teaches techniques that the can be used to create new algorithms to meet future needs. The text includes useful algorithms such as: methods for manipulating common data structures, advanced data structures, network algorithms, and numerical algorithms. It also offers a variety of general problem-solving techniques.

In addition to describing algorithms and approaches, the author offers details on how to analyze the performance of algorithms. The book is filled with exercises that can be used to explore ways to modify the algorithms in order to apply them to new situations. This updated edition of Essential Algorithms:

• Contains explanations of algorithms in simple terms, rather than complicated math
• Steps through powerful algorithms that can be used to solve difficult programming problems
• Helps prepare for programming job interviews that typically include algorithmic questions
• Offers methods can be applied to any programming language
• Includes exercises and solutions useful to both professionals and students
• Provides code examples updated and written in Python and C#

Essential Algorithms has been updated and revised and offers professionals and students a hands-on guide to analyzing algorithms as well as the techniques and applications. The book also includes a collection of questions that may appear in a job interview. The book’s website will include reference implementations in Python and C# (which can be easily applied to Java and C++).