Roberto Nogueira BSd EE, MSd CE
Solution Integrator Experienced - Certified by Ericsson
I Practical Algorithm Design
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 theWar Stories
[ ] 1.6 War Story: PsychicModeling
[ ] 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
[ ] xii CONTENTS
[ ] 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 ofMoore’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 SearchMethods
[ ] 7.6 War Story: Only it is Not a Radio
[ ] 7.7 War Story: Annealing Arrays
[ ] 7.8 Other Heuristic SearchMethods
[ ] 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
10 How to Design Algorithms
[ ] II The Hitchhiker’s Guide to Algorithms
[ ] 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.6 Linear Programming
[ ] 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
[ ] 15.12 Planarity Detection and Embedding
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-Axis 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
[ ] 18.9 Shortest Common Superstring
19 Algorithmic Resources 657
[ ] 19.1 Software Systems
[ ] 19.2 Data Sources
[ ] 19.3 Online Bibliographic Resources
[ ] 19.4 Professional Consulting Services
Bibliography 665
Index 709
