算法設(shè)計(jì)技巧與分析（英文版）

Contents
PART 1 Basic Concepts and Introduction to Algorithms
Chapter 1 Basic Concepts in Algorithmic Analysis
1.1 Introduction
1.2 Historical Background
1.3 Binary Search
1.3.1 Analysis of the binary search algorithm
1.4 Merging Two Sorted Lists
1.5 Selection Sort
1.6 Insertion Sort
1.7 BottomJ.Jp Merge Sorting
1.7.1 Analysis of bottom-up merge sorting
1.8 Time Complexity
1.9 Space Complexity
1.10 optimal Algorithms
1.11 How to Estimate the Running Time of an Algorithm
1.12 Worst case and average case analysis
1.13 Amortized Analysis
1.14 Input Size and Problem Instance
1.15 Exercises
1.16 Bibliographic Notes

Chapter 2 Mathematical Preliminaries
2.1 Sets, Relations and Functions
2.2 Proof Methods
2.3 Logarithms
2.4 Floor and Ceiling Functions
2.5 Factorial and Binomial Coefficients
2.6 The Pigeonhole Principle
2.7 summations
2.8 Recurrence Relations
2.9 Exercises

Chapter 3 Data Structures
3.1 Introduction
3.2 LinkedLists
3.3 Graphs
3.4 Trees
3.5 RootedTYees
3.5.1 Tree traversals
3.6 Binary Trees
3.7 Exercises
3.8 Bibliographic Notes

Chapter 4 Heaps and the Disjoint Sets Data Structures
4.1 Introduction
4.2 Heaps
4.3 Disjoint Sets Data Structures
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.3 Radix Sort
5.4 Integer Exponentiation
5.5 Evaluating Polynomials (Horner’s Rule)
5.6 Generating Permutations
5.7 Finding the Majority Element
5.8 Bibliographic Notes
5.9 Exercises

Chapter 6 Divide and Conquer
6.1 Introduction
6.2 Binary Search
6.3 Mergesort
6.4 Selection: Finding the Median and the kth Smallest Element
6.5 The Divide and Conquer Paradigm
6.6 Quicksort
6.7 Multiplication of Large Integers
6.8 Matrix Multiplication
6.9 The Closest Pair Problem
6.10 Exercises
6.11 Bibliographic Notes

Chapter 7 Dynamic Programming
7.1 Introduction
7.2 The Longest Common Subsequence Problem
7.3 Matrix Chain Multiplication
7.4 The Dynamic Programming Paradigm
7.5 The All-Pairs Shortest Path Problem
7.7 Exercises
7.6 The Knapsack Problem
7.8 Bibliographic Notes

PART 3 First-Cut Techniques
Chapter 8 The Greedy Approach
8.1 Introduction
8.2 The Shortest Path Problem
8.3 Minimum Cost Spanning Trees (Kruskal’s Algorithm)
8.4 Minimum Cost Spanning Trees (Prim’s Algorithm)
8.5 File Compression
8.6 Exercises
8.7 Bibliographic Notes

Chapter 9 Graph Traversal
9.1 Introduction
9.2 Depth-First Search
9.3 Applications of Depth-First Search
9.4 Breadth-First Search
9.5 Applications of Breadth-First Search
9.6 Exercises
9.7 Bibliographic Notes

PART 4 Complexity of Problems
Chapter 10 NP-complete Problems
10.1 Introduction
10.2 The Class P
10.3 The Class NP
10.4 NP-complete Problems
10.5 The Class co-NP
10.6 The Class NPI
10.7 The Relationships Between the Four Classes
10.8 Exercises
10.9 Bibliographic Notes

Chapter 11 Introduction to Computational Complexity
11.1 Introduction
11.2 Model of Computation: The Turing Machine
11.3 k-tape Turing 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
11.7 Reductions
11.8 Completeness
11.9 The Polynomial Time Hierarchy
11.10Exercises
11.11 Bibliographic Notes

Chapter 12 Lower Bounds
12.1 Introduction
12.2 Trivial Lower Bounds
12.3 The Decision Tree Model
12.4 The Algebraic Decision Tree Model
12.5 Linear Time Reductions
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 Bibliographic notes

Chapter 14 Randomized Algorithms
14.1 Introduction
14.2 Las Vegas and Monte Carlo Algorithms
14.3 Randomized Quicksort
14.4 Randomized Selection
14.5 Testing String Equality
14.6 Pattern Matching
14.7 Random Sampling
14.8 Primality Testing
14.9 Exercises
14.10Bibliographic Notes

Chapter 15 Approximation Algorithms
15.1 Introduction
15.2 Basic Definitions
15.3 Difference Bounds
15.4 Relative Performance Bounds
15.5 Polynomial Approximation Schemes
15.6 Fully Polynomial Approximation Schemes
15.7 Exercises
15.8 Bibliographic Notes

PART 6 Iterative Improvement for Domain-Specific Problems
Chapter 16 Network Flow
16.1 Introduction
16.2 Preliminaries
16.3 The Ford-Fulkerson Method
16.4 Maximum Capacity Augmentation
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
17.2 Preliminaries
17.3 The Network Flow Method
17.4 The Hungarian Tree Method for Bipartite Graphs
17.5 Maximum Matching in General Graphs
17.6 An O ( n2.5)Algorithm for Bipartite Graphs
17.7 Exercises
17.8 Bibliographic Notes

PART 7 Techniques in Computational Geometry
Chapter 18 Geometric Sweeping
18.1 Introduction
18.2 Geometric Preliminaries
18.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 Bibliographic Notes

Chapter 19 Voronoi Diagrams
19.1 Introduction
19.2 Nearest-Point Voronoi Diagram
19.3 Applications of the Voronoi Diagram
19.4 Farthest-Point Voronoi Diagram
19.5 Applications of the Farthest-Point Voronoi Diagram
19.6 Exercises
19.7 Bibliographic Notes
Bibliography
Index