Ⅰ 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
鄂公網(wǎng)安備 42010302001612號(hào) 