The Algorithm Design Manual¶

Resources¶

Steven Skiena Homepage

Modules¶

Chapters Checklist¶

1 Introduction To Algorithm Design
- 1.1 Robot Tour Optimization
- 1.2 Selecting the Right Jobs
- 1.3 Reasoning about Correctness
- 1.4 Modeling the Problem
- 1.5 About the War Stories
- 1.6 War Story: Psychic Modeling
- 1.7 Exercises
2 Algorithm Analysis
- 2.1 The Ram Model of Computation
- 2.2 The Big Oh notation
- 2.3 Growth Rates and Dominance Relations
- 2.4 Working with the Big Oh
- 2.5 Reasoning about Efficiency
- 2.6 Logarithms and their Applications
- 2.7 Properties of Logarithms
- 2.8 War Story: Mystery of the Pyramids
- 2.9 Advanced Analysis (*)
- 2.10 Exercises
3 Data Structures
- 3.1 Contiguous vs. Linked Data Structures
- 3.2 Stacks and Queues
- 3.3 Dictionaries
- 3.4 Binary Search Trees
- 3.5 Priority Queues
- 3.6 War Story: Stripping Triangulations
- 3.7 Hashing and Strings
- 3.8 Specialized Data Structures
- 3.9 War Story: String 'em up
- 3.10 Exercises
4 Sorting and Searching
- 4.1 Applications of Sorting
- 4.2 Pragmatics of Sorting
- 4.3 Heapsort: Fast Sorting Via Data Structures
- 4.4 War Story: Give Me a Ticket on an Airplane
- 4.5 Mergesort: Sorting by Divide-and-Conquer
- 4.6 Quicksort: Sorting by Randomization
- 4.7 Distribution Sort: Sorting via Bucketing
- 4.8 War Story: Skiena For the Defense
- 4.9 Binary Search and Related Algorithms
- 4.10 Divide-and-Conquer
- 4.11 Exercises
5 Graph Traversal
- 5.1 Flavors of Graphs
- 5.2 Data Structures for Graphs
- 5.3 War Story: I was a Victim of Moore's Law
- 5.4 War Story: Getting the Graph
- 5.5 Traversing a Graph
- 5.6 Breadth-First Search
- 5.7 Applications of Breadth-First Search
- 5.8 Depth-First Search
- 5.9 Applications of Depth-First Search
- 5.10 Depth-First Search on Directed Graphs
- 5.11 Exercises
6 Weighted Graph Algorithms
- 6.1 Minimum Spanning Trees
- 6.2 War Story: Nothing but Nets
- 6.3 Shortest Paths
- 6.4 War Story: Dialing for Documents
- 6.5 Network Flows and Bipartite Matching
- 6.6 Design Graphs, not Algorithms
- 6.7 Exercises
7 Combinatorial Search and Heuristic Methods
- 7.1 Backtracking
- 7.2 Search Pruning
- 7.3 Sudoku
- 7.4 War Story: Covering Chessboards
- 7.5 Heuristic Search Methods
- 7.6 War Story: only it is not a Radio
- 7.7 War Story: Annealing Arrays
- 7.8 Other Heuristic Search Methods
- 7.9 Parallel Algorithms
- 7.10 War Story: Going Nowhere Fast
- 7.11 Exercises
8 Dynamic Programming
- 8.1 Caching Vs. Computation
- 8.2 Approximate String Matching
- 8.3 Longest Increasing Sequence
- 8.4 War Story: Evolution of the Lobster
- 8.5 the Partition Problem
- 8.6 Parsing Context-Free Grammars
- 8.7 Limitations of Dynamic Programming: Tsp
- 8.8 War Story: What's Past is Prolog
- 8.9 War Story: Text Compression for Bar Codes
- 8.10 Exercises
9 Intractable Problems and Approximation Algorithms
- 9.1 Problems and Reductions
- 9.2 Reductions for Algorithms
- 9.3 Elementary Hardness Reductions
- 9.4 Satisfiability
- 9.5 Creative Reductions
- 9.6 The Art of Proving Hardness
- 9.7 War Story: Hard Against the Clock
- 9.8 War Story: and then I Failed
- 9.9 P vs. NP
- 9.10 Dealing With NP-Complete Problems
- 9.11 Exercises
11 A Catalog of Algorithmic Problems
12 Data Structures
- 12.1 Dictionaries
- 12.2 Priority Queues
- 12.3 Suffix Trees and Arrays
- 12.4 Graph Data Structures
- 12.5 Set Data Structures
- 12.6 Kd-Trees
13 Numerical Problems
- 13.1 Solving Linear Equations
- 13.2 Bandwidth Reduction
- 13.3 Matrix Multiplication
- 13.4 Determinants and Permanents
- 13.5 Constrained and Unconstrained Optimization
- 13.7 Random Number Generation
- 13.8 Factoring and Primality Testing
- 13.9 Arbitrary-Precision Arithmetic
- 13.10 Knapsack Problem
- 13.11 Discrete Fourier Transform
14 Combinatorial Problems
- 14.1 Sorting
- 14.2 Searching
- 14.3 Median and Selection
- 14.4 Generating Permutations
- 14.5 Generating Subsets
- 14.6 Generating Partitions
- 14.7 Generating Graphs
- 14.8 Calendrical Calculations
- 14.9 Job Scheduling
- 14.10 Satisfiability
15 Graph Problems: Polynomial-Time
- 15.1 Connected Components
- 15.2 Topological Sorting
- 15.3 Minimum Spanning Tree
- 15.4 Shortest Path
- 15.5 Transitive Closure and Reduction
- 15.6 Matching
- 15.7 Eulerian Cycle/Chinese Postman
- 15.8 Edge and Vertex Connectivity
- 15.9 Network Flow
- 15.10 Drawing Graphs Nicely
- 15.11 Drawing Trees
16 Graph Problems: Hard Problems
- 16.1 Clique
- 16.2 Independent Set
- 16.3 Vertex Cover
- 16.4 Traveling Salesman Problem
- 16.5 Hamiltonian Cycle
- 16.6 Graph Partition
- 16.7 Vertex Coloring
- 16.8 Edge Coloring
- 16.9 Graph Isomorphism
- 16.10 Steiner Tree
- 16.11 Feedback Edge/Vertex Set
17 Computational Geometry
- 17.1 Robust Geometric Primitives
- 17.2 Convex Hull
- 17.3 Triangulation
- 17.4 Voronoi Diagrams
- 17.5 Nearest Neighbor Search
- 17.6 Range Search
- 17.7 Point Location
- 17.8 Intersection Detection
- 17.9 Bin Packing
- 17.10 Medial-Ax is Transform
- 17.11 Polygon Partitioning
- 17.12 Simplifying Polygons
- 17.13 Shape Similarity
- 17.14 Motion Planning
- 17.15 Maintaining Line Arrangements
- 17.16 Minkowski Sum
18 Set and String Problems
- 18.1 Set Cover
- 18.2 Set Packing
- 18.3 String Matching
- 18.4 Approximate String Matching
- 18.5 Text Compression
- 18.6 Cryptography
- 18.7 Finite State Machine Minimization
- 18.8 Longest Common Substring/Subsequence
19 Algorithmic Resources
- 19.1 Software Systems
- 19.2 Data Sources
- 19.3 Online Bibliographic Resources
- 19.4 Professional Consulting Services