Preface
PART 1 Basic Concepts and Introduction to
Algorithms
Chapter 1 Basic Concepts in Algorithmic Analysis
1.1 Introduction
l.2 Historical BaCkground
1.3 Binary Search
1.3.1 Analysis of the binary search algorithm
1.4 Merging Two Sorted Lists
1.5 Selectinn Sort
1.6 Insertion Sort
1.7 Bottom-Up Merge Sorting
1.7.1 Analysis of bottom-up merge sorting
1.8 Time Complexity
1.8.1 Order of growth
1.8.2 The O-notation
1.8.3 The fl-notation
l.8.4 The e-notation
1.8.5 MamPles
1.8.6 Complekity classes and the o-notation
1.9 Space Complexity
1.10 Optimal Algorithms
1.1l How to Bstimate the Running Time of an Algorithm
1.l1.1 Couliting the number of forrations
l.1l.2 Counting the frequency of basic operatha
1.1l.3 Using recurrence relations
1.l2 Worst case and average case analysis
l.12.1 Wofst case analysis
1.12.2 Average case analysis
l.13 Amedised Analyais
1.14 Input Sise and Problem Instance
1.15 Exercises
1.16 Bibiographic Notes
Chapter 2 Mathematical Preliminaries
2.1 Sots, Reations and Annctions
2.1.1 sets
2.1.2 ffelations
2.1.2.l Equivalence relations
2.1.3 Thnctions
2.2 Proof Mehods
2.2.1 Direct proof
2.2.2 Indirect proof
2.2.3 Proof by colltradiction
2.2.4 Proof by cotillterexample
2.2.5 Mathematical induction
2.3 Logarithms
2.4 Floor and Ceiling Tunctions
2.5 Factorial and Binomial Coefficients
2.5.1 Factorials
2.5.2 Bintalal coefficients
2.6 The Pigeonhole Principle
2.7 Summations
2.7.1 Approkimation of summations by integration
2.8 Recurrence Relations
2.8.1 Solution of linear homogeneous recurrences
2.8.2 Solution of inhomogeneous recurrences
2.8.3 Solation of divide-and-conquer recurrence
2.8.3.1 Expanding the recurrence
2.8.3.2 Sutistitution
2.8.3.3 Change of variables
2.9 Exercises
Chapter 3 Data Structures
3.1 Introdction
3.2 Linked Lists
3.2.1 Stacks ana queues
3.3 Graphs
3.3.1 Representation of graphs
3.3.2 planar graphs
3.4 Trees
3.5 Rooted Trees
3.5.1 Tree traversals
3.6 Binary Trees
3.6.l Some quantitative aspects of binary trees
3.6.2 Binary search trees
3.7 Exercises
3.8 Blbliographic Notes
Chapter 4 Heaps and the Disjoint Sets Data Structure
4.l Iotroduction
4.2 Heaps
4.2.1 Operations on heaps
4.2.2 Creating a heap
4.2.3 Heapsort
4.2.4 Min and max heaps
4.3 Disjoint Sets Data Structures
4.3.1 The union by rank heuristic
4.3.2 Path compression
4.3.3 The union-find algorithms
4.3.4 Analysis of the uninn-find algorithms
4.4 Exercises
4.5 Bibliographic Notes
PART 2 Techniques Based on Recursion
Chapter 5 Induction
5.1 Introduction
5.2 Two Simple Examples
5.2.1 Selection sort
5.2.2 Insertion sort
5.3 Tadix Sort
5.4 Integer Exponentiation
5.5 Evaluating Polynomials (Horner's Rule)
5.6 Generating Permutations
5.6.1 The first algorithm
5.6.2 The second algorithm
5.7 Finding the Majority Element
5.8 Exercises
5.9 Bibliographic Notes
Chapter 6 Divide and Conquer
6.1 Introduction
6.2 Binary Search
6.3 Mergesort
6.3.1 How the algorithm works
6.3.2 Analysis of the mergesort algorithm
6.4 The Divide and Conquer Paradigm
6.5 Selection: Finding the Median and the kth Smallest Element
6.5.l Analysis of the selection algorithm
6.6 Quicksort
6.6.1 A partitinning algorithm.
6.6.2 The sorting algorithm
6.6.3 Analysis of the quicksort algorithm
6.6.3.1 The worst case behavior
6.6.3.2 The average case behavior
6.6.4 Comparison of sorting algorithms
6.7 Multiplication of Large Integers
6.8 Matrin Multiplication
6.8.1 The traditional algorithm
6.8.2 Recursive version
6.8.3 Strassen's algorithm
6.8.4 Comparisons of the three algorithms
6.9 The Closest Pair Prob1em
6.9.1 Time complekity
6.10 Exercises
6.11 BibliograPhic Notes
Chapter 7 Dynamic Programming
7.1 Introduction
7.2 The Longed Common Subsequence Problem
7.3 Matris Chain Multiplication
7.4 The Dynamic Programming Paradigm
7.5 The All-Pairs Shortest Path Problem.
7.6 The Knapsack Problem
7.7 Exercises
7.8 Bibliographic Notes
PART 3 First-Cut Techniques
Chapter 8 The Greedy Approach
8.1 Introduction
8.2 The Shortest Path Problem
8.2.1 A linear time algorithm for dense graphs
8.3 Minimum Cost Spanning nees (Kruskal's Algorithm)
8.4 Minimum Cost Spanning nees (Prim's Algorithm)
8.4.1 A linear time algorithm for dense graphs
8.5 File Compression
8.6 Exercises
8.7 Bibliographic Notes
Chapter 9 Graph Thaversal
9.1 Introduction
9.2 Depth-First Search
9.2.1 Time'complexity of depth-first search
9.3 Applications of Depth-First Search
9.3.1 Graph acyclicity
9.3.2 Topological sorting
9.3.3 Finding articulation points in a graph
9.3.4 Strongly connected components
9.4 Breadth-First Search
9.5 Applications of Breadth-First Sparch
9.6 Exercises
9.7 Bibliographic Notes
PART 4 Complexity of Problems
Chapter 10 NP-Complete Problems
10.l Illtroduction
10.2 The Class P
10.3 The Class NP
10.4 NP-Complete Problems
10.4.1 The satisfiability problem
10.4.2 Vertex cover, independent set and clique problems
10.4.3 More NP-complete Problems
10.5 The Class co-NP
10.6 The Class NPI
10.7 The Relationips Between the Four Classes
l0.8 Exercises
10.9 Biblioaraphic Notes
Chapter 11 Introduction to Computational Complexity
11.1 Introduction
11.2 Mode of Computation: Tlie Turing Machine
11.3 k-tape Thring Machines and Time complexity
11.4 Off-Line Turing Machines and Space Complexity
11.5 Tape Compression and Linear Speed-Up
11.6 Relationships Between complexity Classes
l1.6.1 Space and for hieraxchy theorems.
11.6.2 Padding arguments
ll.7 Reductions
11.8 Completeness
1l.8.1 NLOGSPACE-complete problems
11.8.2 PSPACE-complete problems
11.8.3 P-complete problems
11.8.4 Some conclusions of completeness
11.9 The Polynomial Time Hierarchy
11.10 Exercises
11.11 Bibliographic Notes
Chapter 12 Lower Bouuds
12.1 Introduction
12.2 Trivial Lower Bounds
12.3 The Decision Tree Model
12.3.1 The search problem
12.3.2 The sorting problem
l2.4 The Algebraic Decision Tree Model
l2.4.1 The element uniqueness problem
12.5 Linear Time bouctions
12.5.1 The convex hull problem
12.5.2 The closest pair problem
12.5.3 The Euclidean minimum spanning tree problem
12.6 Exercises
12.7 Bibliographic Notes
PART 5 Coping with Hardness
Chapter 13 Backtracking
13.1 Introduction
13.2 The 3-Coloring Problem
13.3 The 8-Queens Problem
13.4 The General Backtracking Method
13.5 Branch and Bound
13.6 Exercises
13.7 Bib1iographic notes
Chapter 14 Randomized Algorithms
14.l Introduction
14.2 Las Vegas and Moote Carlo Algorithms
14.3 Randomised Quicksort
l4.4 Randomized Selection
l4.5 Testing String Equality
14.6 Pattern Matching
14.7 Random Sampling
l4.8 Primality Testing
14.9 Exercises
14.10 Bibliographic Notes
Chapter 15 Approximation Algorithms
15.1 Introduction
15.2 Basic Definitions
l5.3 Difference Bounds
15.3.1 Planar graph coloring
15.3.2 Hardness result: the knapsack problem
15.4 Relative Performance Bounds
15.4.1 The bin packing problem
15.4.2 The Euclidean traveling salesman problem
l5.4.3 The vertex cover problem
15.4.4 Hardness resu1t: the traveling sa1esman problem
15.5 Polynomial Approximation Schemes
15.5.1 The knapsack problem
15.6 Fully Po1ynomial Approximation Schemes
15.6.1 The subset-sum problem
15.7 Exercises
15.8 BibliograPhic NOtes
PART 6 Iterative Improvement for Domain-Specific
Problems
Chapter 16 Network Flow
16.1 Introduction
16.2 Pre1iminaries
16.3 The Ford-Fulkerson Method
16.4 Mtalmum Capacity Augmelltation
16.5 Shortest Path Augmentation
16.6 Dinic's Algorithm
16.7 The MPM Algorithm
16.8 Exercises
16.9 Bibliographic Notes
Chapter 17 Matching
17.1 Introduction
l7.2 Preliminaries
17.3 Tbe Network Flow Method
17.4 The Hungarian Tree Method for Bipartite Graphs
17.5 Maximum Matching in General Graphs
17.6 An O(n) Algorithm for Bipwtite Graphs
17.7 Exercises
17.8 Bibllogranfor Notes
PART 7 Techniques in Computational Geometry
Chapter 18 Geometric Sweeping
18.1 Introduction
18.2 Geometric Preliminaries
l8.3 Computing the Intersections of Line Segments
18.4 The Convex Hull Problem
18.5 Computing the Diameter of a Set of Points
18.6 Exercises
18.7 Bib1iographic Notes
Chapter 19 Voronoi Diagrams
l9.1 Introduction
19.2 Nearest-Point Voronoi Diagram
19.2.1 Delaunay triangulation
19.2.2 Construction of the Voronoi diagram
l9.3 Applications of the Voronoi Diagram
19.3.1 Computing the convex hull
19.3.2 All nearest neighbors
19.3.3 The Euclidean minimum spanning tree
19.4 Farthed-Point Voronoi Diagram
19.4.1 Construction of the farthest-point Voronoi diagram
19.5 Applications of the Farthest-Point Voronoi Diagram
19.5.1 All farthest neighbors
19.5.2 Smallest enclosing circle
19.6 Exercises
l9.7 Bibliographic Notes
Bibliography
Index
鄂公网安备 42010302001612号 