- 高等教育出版社
- 9787040146196
- 1
- 248994
- 平装
- 特殊
- 2004-07-15
- 510
- 378
- 工学
- 计算机科学与技术
本书提供了在学习现代计算机算法时经常会遇到的许多问题的答案，可以帮助读者更好地理解、掌握算法分析与设计课程。本书包括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
