The Algorithm Design Manual

Resources

• Steven Skiena Homepage

Modules

• [[14-modeling-the-problem]]
• [[21-the-ram-model-of-computation]]
• [[22-the-big-oh-notation]]
• [[23-growth-rate-and-dominance-relations]]
• [[24-working-with-the-big-oh]]
• [[27-properties-of-logarithms]]
• [[31-contiguous-vs-linked-data-structures]]

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