Introduction to algorithams: a creative approach /
Udi manber
- New York : Addison Wesley , c1989.
- xiv, 478 p. ill. ;
Chapter 1 Introduction Chapter 2 Mathematical induction 2.1 Introduction 2.2 Tliree Simple Examples 2.3 Counting Regions in the Plane 2.4 A Simple Coloring Problem 2.5 A More Complicated Summation Problem 2.6 A Simple Inequality 2.7 Euler's Fonnula 2.8 A Problem in Graph Theory 2.9 Gray Codes 2.10 Finding Edge-Disjoint Paths in a Graph 2.11 Arithmetic versus Geometric Mean Theoiem 2.12 Loop Invariants: Converting a Decimal Number to Binary 2.13 Common Errors 2.14 Summary Bibliogiaphic Notes and Further Reading Exercises Chapter 3 Analysis of Algoi ithms 3.1 Introduction 3.2 The 0 Notation 3.3 Time and Space Complexity 3.4 Summations 3.5 Recurrence Relations 3.5.1 Intelligent Guesses 3.5.2 Divide and Cotiquer Relations 3.5.3 Recuirence Relations with Full History 3.6 Useful Facts 3.7 Summary . Bibliographic Notes and Further Reading Exercises Chapter 4 Data Structures 4.1 Introduction 4.2 Elementary Data Structures 4.2.1 Elements 4.2.2 Arrays 4.2.3 Records 4.2.4 Linked Lists 4.3 Trees 4.3.1 Representation of Trees 4.3.2 Heaps 4.3.3 Binary Search Trees 4.3.4 AVL Trees 4.4 Hashing 4.5 The Union-Find Problem 4.6 Graphs 4.7 Summary Bibliographic Notes and Further Reading Exercises Chapter S Design of Algorithms by Induction 5.1 Introduction 5.2 Evaluating Polynomials 5.3 Maximal Induced Subgraph 5.4 Finding One-to-One Mappings 5.5 The Celebrity Problem 5.6 A Divide-and-Conquer Algorithm: The Skyline Problem 5.7 Computing Balance Factors in Binary Trees 5.8 Finding the Maximum Consecutive Subsequence 5.9 Strengthening the Induction Hypothesis 5.10 Dynamic Programming: The Knapsack Problem 5.11 Common Errors 5.12 Summary * Bibliographic Notes and Further Reading Exercises Chapter 6 Algorithms Involving Sequences and Sets 6.1 Introduction 6.2 Binary Search and Variations 6.3 Interpolation Search 6.4 Sorting 6.4.1 Bucket Sort and Radix Sort 6.4.2 Insertion Sort and Selection Sort 6.4.3 Mergesort 6.4.4 Quicksort 6.4.5 Heapsoit 6.4.6 A Lower Bound for Sorting 6.5 Order Statistics 6.5.1 Maximum and Minimum Elements 6.5.2 Finding the ftth-Smallest Element 6.6 Data Compression 6.7 String Matching 6.8 Sequence Comparisons 6.9 Probabilistic Algorithms 6.9.1 Random Numbers 6.9.2 A Coloring Problem 6.9.3 A Technique for Tiansfonning Probabilistic Algorithms into Deterministic Algorithms 6.10 Finding a Majority 6.11 Three Problems Exhibiting Interesting Proof Techniques 6.11.1 Longest Increasing Subsequence 6.11.2 Finding the Two Largest Elements in a Set 6.11.3 Computing the Mode of a Multiset 6.12 Summary Bibliographic Notes and Further Reading Exercises Chapter 7 Graph Algorithms 7.1 Introduction 7.2 Eulerian Graphs 7.3 Graph Traversals 7.3.1 Depth-First Search 7.3.2 Breadth-First Search 7.4 Topological Sorting 7.5 Single-Source Shortest Paths 7.6 Minimum-Cost Spanning Trees 7.7 All Shortest Paths 7.8 Transitive Closure 7.9 Decompositions of Graphs 7.9.1 Biconnected Components 7.9.2 Strongly Connected Components 7.9.3 Examples of the Use of Graph Decomposition 7.10 Matching 7.10.1 Perfect Matching in Very Dense Graphs 7.10.2 Bipartite Matching 7.11 Network Flows 7.12 Hamiltonian Tours 7.12.1 Reversed Induction 7.12.2 Finding Hamiltonian Cycles in Very Dense Graphs 7.13 Summary Bibliographic Notes and Further Reading Exercises Chapter 8 Geomelric Algorithms 8.1 Introduction 8.2 Delemiining Whether a Point Is Inside a Polygon 8.3 Constructing Simple Polygons 8.4 Convex Hulls 8.4.1 A Straightforward Approach 8.4.2 Gift Wrapping 8.4.3 Graham's Scan 8.5 Closest Pair 8.6 Intersections of Horizontal and Vertical Line Segments 8.7 Summary Bibliographic Notes and Furtiier Reading Exercises Chapter 9 Algebraic and Numeric Algorithms 9.1 Introduction 9.2 Exponentiation 9.3 Euclid's Algorithm 9.4 Polynomial Multiplication 9.5 Matrix Multiplication 9.5.1 Winograd's Algorithm 9.5.2 Strasseti's Algorithm 9.5.3 Boolean Matrices 9.6 The Fast Fourier Transfomi 9.7 Summary Bibliographic Notes and Further Reading Exercises i3hapter10 Redtictlons 10.1 Introduction 1(^2 Examples of Reductions 10.2.1 A Simple String-Matching Problem 10.2.2 Systems of Distinct Representatives 10.2.3 A Reduction Involving Sequence Cotnparisons 10.2.4 Finding a Tiiangle in 1 Indirected Graphs 10.3 Reductions Involving Linear Progr.immiug 10.3.1 Introduction atid nefiniiions 10.3.2 Examples of Reductions to Linear Programming 10.4 Rcduclion.s for Lower Bounds 10.4.1 A Lower Bound for Finding Simple Polygons 10.4.2 Simple Reductions Involving Matrices 10.5 Common En ors 10.6 Summary Bibliographic Notes and Further Reading Exercises Chapter I f NP-Coiopletetiess 1 1.1 Introduction 11.2 Polynomial-Time Reductions 11.3 Nondclemiinism and Cook's I heotem 11.4 Examples of NP-Cuinplelenc.ss Pioofs 11.4.1 Veitex Cover 11.4.2 Dominating Set 11.4.3 3SAr 11.4.4 Clkjue 11.4.5 3-Coioiing 1 1.4.6 General Observations 1! .4.7 Mote NP-Complete Problems 11.5 rechniques Foi [dealing with NP-Complete Problems 11.5.1 Backtracking and Biancii-and-Boimd 11.5.2 Appioxirnation Algoritlims with Guaianteed 11.6 Summary Perfoimance Bibliographic Notes and Further Reading Exercises Chapter 12 Parallel Alyorilhins 12.1 Intioduction 12.2 Models ofl'aiallel Computation 12.3 Algorithms lor Shatcd-Memory Machines 12.3.1 Parallel Addition 12.3.2 Maxinuim-Finding Algorithms 12.3.3 The Parallcl-Pielix Problem 12.3.4 Finding Ratiks in Linked Lists 12.3.5 The Euler's Tour Technique * 12.4 Algol itiims for Interconnection Networks 12.4.1 Sorting r)n an Array 12.4.2 Sorting Networks 12.4.3 Finding the Aith-Smallest Element on a Tree 12.4.4 Maliix Multiplication on the Mesh 12.4.5 Routing in a Hypercube 12.5 Systolic Computation 12.5.1 Matrix-Vector Multiplication 12.5.2 The Convolution Problem 12.5.3 Sequence Comparisons 12.6 Summary Bibliographic Notes and Further Reading Exercises