dhruv's wiki
T

# The Algorithm Design Manual

## Chapters Checklist

• 1 Introduction To Algorithm Design
• 1.1 Robot Tour Optimization
• 1.2 Selecting the Right Jobs
• 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.6 Logarithms and their Applications
• 2.7 Properties of Logarithms
• 2.8 War Story: Mystery of the Pyramids
• 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.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