About the Book

This book provides an easy-to-read introduction to computer algorithms. It describes a number of important classical algorithms and tells when each is appropriate. It explains how to analyze algorithms to understand their behavior. Most importantly it teaches techniques that the reader can use to create new algorithms to meet future needs.

About the Author

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.

Table of Contents:
Introduction Chapter 1 Algorithm Basics Approach Algorithms and Data Structures Pseudocode Algorithm Features Big O Notation Common Runtime Functions Visualizing Functions Practical Considerations Summary Exercises Chapter 2 Numerical Algorithms Randomizing Data Generating Random Values Randomizing Arrays Generating Nonuniform Distributions Finding Greatest Common Divisors Performing Exponentiation Working with Prime Numbers Finding Prime Factors Finding Primes Testing for Primality Performing Numerical Integration The Rectangle Rule The Trapezoid Rule Adaptive Quadrature Monte Carlo Integration Finding Zeros Summary Exercises Chapter 3 Linked Lists Basic Concepts Singly Linked Lists Iterating Over the List Finding Cells Using Sentinels Adding Cells at the Beginning Adding Cells at the End Inserting Cells After Other Cells Deleting Cells Doubly Linked Lists Sorted Linked Lists Linked-List Algorithms Copying Lists Sorting with Insertionsort Linked List Selectionsort Multithreaded Linked Lists Linked Lists with Loops Marking Cells Using Hash Tables List Retracing List Reversal Tortoise and Hare Loops in Doubly Linked Lists Summary Exercises Chapter 4 Arrays Basic Concepts One-dimensional Arrays Finding Items Finding Minimum, Maximum, and Average Inserting Items Removing Items Nonzero Lower Bounds Two Dimensions Higher Dimensions Triangular Arrays Sparse Arrays Find a Row or Column Get a Value Set a Value Delete a Value Matrices Summary Exercises Chapter 5 Stacks and Queues Stacks Linked-List Stacks Array Stacks Double Stacks Stack Algorithms Queues Linked-List Queues Array Queues Specialized Queues Summary Exercises Chapter 6 Sorting O(N2) Algorithms Insertionsort in Arrays Selectionsort in Arrays Bubblesort O(N log N) Algorithms Heapsort Quicksort Mergesort Sub O(N log N) Algorithms Countingsort Bucketsort Summary Exercises Chapter 7 Searching Linear Search Binary Search Interpolation Search Summary Exercises Chapter 8 Hash Tables Hash Table Fundamentals Chaining Open Addressing Removing Items Liner Probing Quadratic Probing Pseudorandom Probing Double Hashing Ordered Hashing Summary Exercises Chapter 9 Recursion Basic Algorithms Factorial Fibonacci Numbers Tower of Hanoi Graphical Algorithms Koch Curves Hilbert Curve Sierpin´ ski Curve Gaskets Backtracking Algorithms Eight Queens Problem Knight's Tour Selections and Permutations Selections with Loops Selections with Duplicates Selections Without Duplicates Permutations with Duplicates Permutations Without Duplicates Recursion Removal Tail Recursion Removal Storing Intermediate Values General Recursion Removal Summary Exercises Chapter 10 Trees Tree Terminology Binary Tree Properties Tree Representations Building Trees in General Building Complete Trees Tree Traversal Preorder Traversal Inorder Traversal Postorder Traversal Depth-first Traversal Traversal Run Times Sorted Trees Adding Nodes Finding Nodes Deleting Nodes Threaded Trees Building Threaded Trees Using Threaded Trees Specialized Tree Algorithms The Animal Game Expression Evaluation Quadtrees Tries Summary Exercises Chapter 11 Balanced Trees AVL Trees Adding Values Deleting Values 2-3 Trees Adding Values Deleting Values B-Trees Adding Values Deleting Values Balanced Tree Variations Top-down B-trees B+trees Summary Exercises Chapter 12 Decision Trees Searching Game Trees Minimax Initial Moves and Responses Game Tree Heuristics Searching General Decision Trees Optimization Problems Exhaustive Search Branch and Bound Decision Tree Heuristics Other Decision Tree Problems Summary Exercises Chapter 13 Basic Network Algorithms Network Terminology Network Representations Traversals Depth-first Traversal Breadth-first Traversal Connectivity Testing Spanning Trees Minimal Spanning Trees Finding Paths Finding Any Path Label-Setting Shortest Paths Label-Correcting Shortest Paths All-Pairs Shortest Paths Summary Exercises Chapter 14 More Network Algorithms Topological Sorting Cycle Detection Map Coloring Two-coloring Three-coloring Four-coloring Five-coloring Other Map-coloring Algorithms Maximal Flow Work Assignment Minimal Flow Cut Summary Exercises Chapter 15 String Algorithms Matching Parentheses Evaluating Arithmetic Expressions Building Parse Trees Pattern Matching DFAs Building DFAs for Regular Expressions NFAs String Searching Calculating Edit Distance Summary Exercises Chapter 16 Cryptography Terminology Transposition Ciphers Row/column Transposition Column Transposition Route Ciphers Substitution Ciphers Caesar Substitution Vigenère Cipher Simple Substitution One-Time Pads Block Ciphers Substitution-Permutation Networks Feistel Ciphers Public-Key Encryption and RSA Euler's Totient Function Multiplicative Inverses An RSA Example Practical Considerations Other Uses for Cryptography Summary Exercises Chapter 17 Complexity Theory Notation Complexity Classes Reductions 3SAT Bipartite Matching NP-Hardness Detection, Reporting, and Optimization Problems Detection ≤p Reporting Reporting ≤p Optimization Reporting ≤p Detection Optimization Reporting NP-Complete Problems Summary Exercises Chapter 18 Distributed Algorithms Types of Parallelism Systolic Arrays Distributed Computing Multi-CPU Processing Race Conditions Deadlock Quantum Computing Distributed Algorithms Debugging Distributed Algorithms Embarrassingly Parallel Algorithms Mergesort Dining Philosophers The Two Generals Problem Byzantine Generals Consensus Leader Election Snapshot Clock Synchronization Summary Exercises Chapter 19 Interview Puzzles Asking Interview Puzzle Questions Answering Interview Puzzle Questions Summary Exercises Appendix A Summary of Algorithmic Concepts Appendix B Solutions to Exercises Glossary Index