本書是國際著名算法專家李德財教授主編的系列叢書“Lecture Notes Series onComputing”中的一本。本書涵蓋了絕大多數算法設計中的一般技術，在表達每一種技術時，闡述它的應用背景，注意用與其他技術比較的方法說明它的特征，并提供大量相應實際問題的例子。全書分七部分19章，從算法設計和算法分析的基本概念和方法入手，先后介紹了遞歸技術、分治、動態規劃、貪心算法、圖的遍歷等技術，并且對NP完全問題進行了基本但清楚的討論。
本書是國際著名算法專家李德財教授主編的系列叢書“Lecture Notes Series onComputing”中的一本。本書涵蓋了絕大多數算法設計中的一般技術，在表達每一種技術時，闡述它的應用背景，注意用與其他技術比較的方法說明它的特征，并提供大量相應實際問題的例子。本書同時也強調了對每一種算法的詳細的復雜性分析。 本書包含以下幾部分 基本概念和算法導引 基于遞歸的技術 最先割技術 問題的復雜性 克服困難性 域指定問題的迭代改進 計算幾何技術
M．H．Alsuwaiyel在沙特阿拉伯的King Fahd University ofPetroleum＆Minerals(KFUPM，皇家法哈德石油礦業大學)完成大學學業，在南加州(USC)大學獲得計算機科學碩士和博士學位。作者曾任KFUPM的計算機科學系主任、工程與計算機學院院長。他在沙特阿拉伯有廣泛的學術影響，是政府(包括內務部和國防部在內)的高級顧問。
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
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 SmallestElement
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
新書資訊