本书提供了在学习现代计算机算法时经常会遇到的许多问题的答案，可以帮助读者更好地理解、掌握算法分析与设计课程。本书包括360多个练习题，这些练习题不仅涉及到一些经典问题，而且包括一些重要的应用程序中的热点问题，如文字处理中的段落排版、数据压缩、数据库系统和Internet搜索引擎等方面的算法问题，这些都是现代软件系统的基本组成部分。
本书可作为高等学校计算机科学与技术类专业、数学及信息与计算科学专业本科生和研究生“算法分析与设计”课程的辅助教材，也可供其他专业涉及算法设计与应用的研究和开发人员学习参考。
- Foreword
- Preface
- Chapter 1 Mathematical Foundation
- 1.1 Growth of Functions1
- 1.1.1 O-notation (Big-O)
- 1.1.2 -notation (Big-Omega)
- 1.1.3 -notation (Big-Theta)
- 1.2 Recurrences
- 1.2.1 Substitution Method
- 1.2.2 Iteration Method
- 1.2.3 Recursion-tree Method
- 1.2.4 Master Method
- 1.2.5 Other Recurrences
- 1.3 Exercises & Solutions
- Chapter 2 Sorting and Selection
- 2.1 Sorting
- 2.1.1 Insertion Sort
- 2.1.2 Selection Sort
- 2.1.3 Mergesort
- 2.1.4 Heapsort
- 2.1.5 Priority Queue
- 2.1.6 Quicksort
- 2.1.7 Counting Sort
- 2.1.8 Radix Sort
- 2.1.9 Bucket Sort
- 2.2 Selection
- 2.2.1 Maximum and Minimum
- 2.2.2 Expected Selection
- 2.2.3 Worst-case Linear Selection
- 2.3 Exercises & Solutions
- Chapter 3 Data Structures
- 3.1 Elementary Data Structures
- 3.1.1 Stacks and Queues
- 3.1.2 Linked Lists
- 3.2 Dynamic Sets and Searching
- 3.2.1 Hash Tables
- 3.2.2 Binary Search Trees
- 3.2.3 Red-black Trees
- 3.2.4 Augmenting Data Structures
- 3.3 Exercises & Solutions
- Chapter 4 Advanced Data Structures
- 4.1 B-Trees
- 4.1.1 Searching a B-tree
- 4.1.2 Creating a B-tree
- 4.2 Binomial Heaps
- 4.2.1 Finding The Minimum Key
- 4.2.2 Uniting Two Binomial Heaps
- 4.3 Fibonacci Heaps
- 4.3.1 Inserting a Node
- 4.3.2 Uniting Two Fibonacci Heaps
- 4.3.3 Extracting a Minimum Node
- 4.4 Data Structures for Disjoint Sets
- 4.5 Exercises & Solutions
- Chapter 5 Advanced Design and Analysis Techniques
- 5.1 Divide-and-Conquer
- 5.1.1 Maximum and Minimum
- 5.1.2 Integer Multiplication
- 5.1.3 Strassen Matrix Multiplication
- 5.2 Dynamic Programming
- 5.2.1 String reconstruction Problem
- 5.2.2 All Pairs Shortest Paths
- 5.2.3 Traveling Salesman Problems
- 5.3 Greedy Algorithms
- 5.3.1 Horn Formula
- 5.3.2 Huffman Coding
- 5.3.3 The Set Cover Problem
- 5.4 Amortized Analysis
- 5.4.1 The aggregate Method
- 5.4.2 The accounting Method
- 5.4.3 The potential Method
- 5.4.4 Incrementing and Decrementing
- 5.5 Exercises & Solutions
- Chapter 6 Graph Algorithms
- 6.1 Elementary Graph Algorithms
- 6.1.1 Data Structures for Graphs
- 6.1.2 Depth-first Search
- 6.1.3 Breadth-first Search
- 6.1.4 Topological Sort
- 6.1.5 Strongly Connected Components
- 6.2 Minimum Spanning Trees
- 6.2.1 Boruvka’s Algorithm
- 6.2.2 Jarnik’s Algorithm
- 6.2.3 Prim’s Algorithm
- 6.2.4 Kruskal’s Algorithm
- 6.3 Single-Source Shortest Paths
- 6.3.1 Bellman-Ford Algorithm
- 6.3.2 SSSP in DAG
- 6.3.3 Dijkstra’s Algorithm
- 6.4 All-Pairs Shortest Paths
- 6.4.1 Johnson’s Algorithm
- 6.4.2 Dynamic Programmig
- 6.4.3 Divide and Conquer
- 6.4.4 Shortest Path and Matrix Multiplication
- 6.4.5 Floyd-Warshall’s Algorithm
- 6.5 Exercises & Solutions
- Bibliograph
