Ⅰ 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 the Wax 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： Stringem 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 Moores 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： Whats 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
Ⅱ The Hitchhikers 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
19.1 Software Systems
19.2 Data Sources
19.3 Online Bibliographic Resources
19.4 Professional Consulting Services
Bibliography
鄂公网安备 42010302001612号 