本书是国际著名算法专家李德财教授主编的系列丛书“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