Skiena The Algorithm Design Manual

• Preface
• Contents
• Introduction to Algorithm Design
  • Robot Tour Optimization
  • Selecting the Right Jobs
  • Reasoning about Correctness
  • Modeling the Problem
  • About the War Stories
  • War Story: Psychic Modeling
  • Exercises
• Algorithm Analysis
  • The RAM Model of Computation
  • The Big Oh Notation
  • Growth Rates and Dominance Relations
  • Working with the Big Oh
  • Reasoning About Efficiency
  • Logarithms and Their Applications
  • Properties of Logarithms
  • War Story: Mystery of the Pyramids
  • Advanced Analysis (*)
  • Exercises
• Data Structures
  • Contiguous vs. Linked Data Structures
  • Stacks and Queues
  • Dictionaries
  • Binary Search Trees
  • Priority Queues
  • War Story: Stripping Triangulations
  • Hashing and Strings
  • Specialized Data Structures
  • War Story: String 'em Up
  • Exercises
• Sorting and Searching
  • Applications of Sorting
  • Pragmatics of Sorting
  • Heapsort: Fast Sorting via Data Structures
  • War Story: Give me a Ticket on an Airplane
  • Mergesort: Sorting by Divide-and-Conquer
  • Quicksort: Sorting by Randomization
  • Distribution Sort: Sorting via Bucketing
  • War Story: Skiena for the Defense
  • Binary Search and Related Algorithms
  • Divide-and-Conquer
  • Exercises
• Graph Traversal
  • Flavors of Graphs
  • Data Structures for Graphs
  • War Story: I was a Victim of Moore's Law
  • War Story: Getting the Graph
  • Traversing a Graph
  • Breadth-First Search
  • Applications of Breadth-First Search
  • Depth-First Search
  • Applications of Depth-First Search
  • Depth-First Search on Directed Graphs
  • Exercises
• Weighted Graph Algorithms
  • Minimum Spanning Trees
  • War Story: Nothing but Nets
  • Shortest Paths
  • War Story: Dialing for Documents
  • Network Flows and Bipartite Matching
  • Design Graphs, Not Algorithms
  • Exercises
• Combinatorial Search and Heuristic Methods
  • Backtracking
  • Search Pruning
  • Sudoku
  • War Story: Covering Chessboards
  • Heuristic Search Methods
  • War Story: Only it is Not a Radio
  • War Story: Annealing Arrays
  • Other Heuristic Search Methods
  • Parallel Algorithms
  • War Story: Going Nowhere Fast
  • Exercises
• Dynamic Programming
  • Caching vs. Computation
  • Approximate String Matching
  • Longest Increasing Sequence
  • War Story: Evolution of the Lobster
  • The Partition Problem
  • Parsing Context-Free Grammars
  • Limitations of Dynamic Programming: TSP
  • War Story: What's Past is Prolog
  • War Story: Text Compression for Bar Codes
  • Exercises
• Intractable Problems and Approximation Algorithms
  • Problems and Reductions
  • Reductions for Algorithms
  • Elementary Hardness Reductions
  • Satisfiability
  • Creative Reductions
  • The Art of Proving Hardness
  • War Story: Hard Against the Clock
  • War Story: And Then I Failed
  • P vs. NP
  • Dealing with NP-complete Problems
  • Exercises
• How to Design Algorithms
• A Catalog of Algorithmic Problems
• Data Structures
  • Dictionaries
  • Priority Queues
  • Suffix Trees and Arrays
  • Graph Data Structures
  • Set Data Structures
  • Kd-Trees
• Numerical Problems
  • Solving Linear Equations
  • Bandwidth Reduction
  • Matrix Multiplication
  • Determinants and Permanents
  • Constrained and Unconstrained Optimization
  • Linear Programming
  • Random Number Generation
  • Factoring and Primality Testing
  • Arbitrary-Precision Arithmetic
  • Knapsack Problem
  • Discrete Fourier Transform
• Combinatorial Problems
  • Sorting
  • Searching
  • Median and Selection
  • Generating Permutations
  • Generating Subsets
  • Generating Partitions
  • Generating Graphs
  • Calendrical Calculations
  • Job Scheduling
  • Satisfiability
• Graph Problems: Polynomial-Time
  • Connected Components
  • Topological Sorting
  • Minimum Spanning Tree
  • Shortest Path
  • Transitive Closure and Reduction
  • Matching
  • Eulerian Cycle/Chinese Postman
  • Edge and Vertex Connectivity
  • Network Flow
  • Drawing Graphs Nicely
  • Drawing Trees
  • Planarity Detection and Embedding
• Graph Problems: Hard Problems
  • Clique
  • Independent Set
  • Vertex Cover
  • Traveling Salesman Problem
  • Hamiltonian Cycle
  • Graph Partition
  • Vertex Coloring
  • Edge Coloring
  • Graph Isomorphism
  • Steiner Tree
  • Feedback Edge/Vertex Set
• Computational Geometry
  • Robust Geometric Primitives
  • Convex Hull
  • Triangulation
  • Voronoi Diagrams
  • Nearest Neighbor Search
  • Range Search
  • Point Location
  • Intersection Detection
  • Bin Packing
  • Medial-Axis Transform
  • Polygon Partitioning
  • Simplifying Polygons
  • Shape Similarity
  • Motion Planning
  • Maintaining Line Arrangements
  • Minkowski Sum
• Set and String Problems
  • Set Cover
  • Set Packing
  • String Matching
  • Approximate String Matching
  • Text Compression
  • Cryptography
  • Finite State Machine Minimization
  • Longest Common Substring/Subsequence
  • Shortest Common Superstring
• Algorithmic Resources
  • Software Systems
  • Data Sources
  • Online Bibliographic Resources
  • Professional Consulting Services
• Bibliography
• Index