The Algorithm Design Manual
Contents
u Techniques
u Introduction to Algorithms
u Correctness and Efficiency
u Correctness
u Efficiency
u Expressing Algorithms
u Keeping Score
u The RAM Model of Computation
u Best, Worst, and Average-Case Complexity
u The Big Oh Notation
u Growth Rates
u Logarithms
u Modeling the Problem
u About the War Stories
u War Story: Psychic Modeling
u Exercises
u Data Structures an...
Contents
u Techniques
u Introduction to Algorithms
u Correctness and Efficiency
u Correctness
u Efficiency
u Expressing Algorithms
u Keeping Score
u The RAM Model of Computation
u Best, Worst, and Average-Case Complexity
u The Big Oh Notation
u Growth Rates
u Logarithms
u Modeling the Problem
u About the War Stories
u War Story: Psychic Modeling
u Exercises
u Data Structures and Sorting
u Fundamental Data Types
u Containers
u Dictionaries
u Binary Search Trees
u Priority Queues
u Specialized Data Structures
u Sorting
u Applications of Sorting
u Approaches to Sorting
u Data Structures
u Incremental Insertion
u Divide and Conquer
u Randomization
u Bucketing Techniques
u War Story: Stripping Triangulations
u War Story: Mystery of the Pyramids
u War Story: String 'em Up
u Exercises
u Breaking Problems Down
u Dynamic Programming
u Fibonacci numbers
u The Partition Problem
u Approximate String Matching
u Longest Increasing Sequence
u Minimum Weight Triangulation
u Limitations of Dynamic Programming
u War Story: Evolution of the Lobster
u War Story: What's Past is Prolog
u War Story: Text Compression for Bar Codes
u Divide and Conquer
u Fast Exponentiation
u Binary Search
u Square and Other Roots
u Exercises
u Graph Algorithms
u The Friendship Graph
u Data Structures for Graphs
u War Story: Getting the Graph
u Traversing a Graph
u Breadth-First Search
u Depth-First Search
u Applications of Graph Traversal
u Connected Components
u Tree and Cycle Detection
u Two-Coloring Graphs
u Topological Sorting
u Articulation Vertices
u Modeling Graph Problems
u Minimum Spanning Trees
u Prim's Algorithm
u Kruskal's Algorithm
u Shortest Paths
u Dijkstra's Algorithm
u All-Pairs Shortest Path
u War Story: Nothing but Nets
u War Story: Dialing for Documents
u Exercises
u Combinatorial Search and Heuristic Methods
u Backtracking
u Constructing All Subsets
u Constructing All Permutations
u Constructing All Paths in a Graph
u Search Pruning
u Bandwidth Minimization
u War Story: Covering Chessboards
u Heuristic Methods
u Simulated Annealing
u Traveling Salesman Problem
u Maximum Cut
u Independent Set
u Circuit Board Placement
u Neural Networks
u Genetic Algorithms
u War Story: Annealing Arrays
u Parallel Algorithms
u War Story: Going Nowhere Fast
u Exercises
u Intractable Problems and Approximations
u Problems and Reductions
u Simple Reductions
u Hamiltonian Cycles
u Independent Set and Vertex Cover
u Clique and Independent Set
u Satisfiability
u The Theory of NP-Completeness
u 3-Satisfiability
u Difficult Reductions
u Integer Programming
u Vertex Cover
u Other NP-Complete Problems
u The Art of Proving Hardness
u War Story: Hard Against the Clock
u Approximation Algorithms
u Approximating Vertex Cover
u The Euclidean Traveling Salesman
u Exercises
u How to Design Algorithms
u Resources
u A Catalog of Algorithmic Problems
u Data Structures
u Dictionaries
u Priority Queues
u Suffix Trees and Arrays
u Graph Data Structures
u Set Data Structures
u Kd-Trees
u Numerical Problems
u Solving Linear Equations
u Bandwidth Reduction
u Matrix Multiplication
u Determinants and Permanents
u Constrained and Unconstrained Optimization
u Linear Programming
u Random Number Generation
u Factoring and Primality Testing
u Arbitrary-Precision Arithmetic
u Knapsack Problem
u Discrete Fourier Transform
u Combinatorial Problems
u Sorting
u Searching
u Median and Selection
u Generating Permutations
u Generating Subsets
u Generating Partitions
u Generating Graphs
u Calendrical Calculations
u Job Scheduling
u Satisfiability
u Graph Problems: Polynomial-Time
u Connected Components
u Topological Sorting
u Minimum Spanning Tree
u Shortest Path
u Transitive Closure and Reduction
u Matching
u Eulerian Cycle / Chinese Postman
u Edge and Vertex Connectivity
u Network Flow
u Drawing Graphs Nicely
u Drawing Trees
u Planarity Detection and Embedding
u Graph Problems: Hard Problems
u Clique
u Independent Set
u Vertex Cover
u Traveling Salesman Problem
u Hamiltonian Cycle
u Graph Partition
u Vertex Coloring
u Edge Coloring
u Graph Isomorphism
u Steiner Tree
u Feedback Edge/Vertex Set
u Computational Geometry
u Robust Geometric Primitives
u Convex Hull
u Triangulation
u Voronoi Diagrams
u Nearest Neighbor Search
u Range Search
u Point Location
u Intersection Detection
u Bin Packing
u Medial-Axis Transformation
u Polygon Partitioning
u Simplifying Polygons
u Shape Similarity
u Motion Planning
u Maintaining Line Arrangements
u Minkowski Sum
u Set and String Problems
u Set Cover
u Set Packing
u String Matching
u Approximate String Matching
u Text Compression
u Cryptography
u Finite State Machine Minimization
u Longest Common Substring
u Shortest Common Superstring
u Algorithmic Resources
u Software systems
u LEDA
u Netlib
u Collected Algorithms of the ACM
u The Stanford GraphBase
u Combinatorica
u Algorithm Animations with XTango
u Programs from Books
u Discrete Optimization Algorithms in Pascal
u Handbook of Data Structures and Algorithms
u Combinatorial Algorithms for Computers and Calculators
u Algorithms from P to NP
u Computational Geometry in C
u Algorithms in C++
u Data Sources
u Textbooks
u On-Line Resources
u Literature
u People
u Software
u Professional Consulting Services
u References
u Index
u About this document ...
Help file produced by WebTwin (www.webtwin.com) HTML->WinHelp converter. This text does not appear in the registered version.
Steven Skiena (1961-, http://www.cs.sunysb.edu/~skiena/) is a Professor of Computer Science in State University of New York at Stony Brook