简介
本书提供了在学习现代计算机算法时经常会遇到的许多问题的答案，可以帮助读者更好地理解、掌握算法分析与设计课程。本书包括360多个练习题，这些练习题不仅涉及到一些经典问题，而且包括一些重要的应用程序中的热点问题，如文字处理中的段落排版、数据压缩、数据库系统和Internet搜索引擎等方面的算法问题，这些都是现代软件系统的基本组成部分。
本书可作为高等学校计算机科学与技术类专业、数学及信息与计算科学专业本科生和研究生“算法分析与设计”课程的辅助教材，也可供其他专业涉及算法设计与应用的研究和开发人员学习参考。
目录
书名页 1
版权页 2
Foreword 3
Preface 4
Contents 6
Chapter 1Mathematical Foundation 9
1.1 Growth of Functions 9
1.1.1 O-notation (Big-O) 9
1.1.2 -notation (Big-Omega) 10
1.1.3 Θ-notation (Big-Theta) 11
1.2 Recurrences 12
1.2.1 Substitution Method 12
1.2.2 Iteration Method 13
1.2.3 Recursion-tree Method 14
1.2.4 Master Method 15
1.2.5 Other Recurrences 15
1.3 Exercises & Solutions 15
Chapter 2Sorting and Selection 65
2.1 Sorting 65
2.1.1 Insertion Sort 65
2.1.2 Selection Sort 66
2.1.3 Mergesort 67
2.1.4 Heapsort 68
2.1.5 Priority Queue 69
2.1.6 Quicksort 71
2.1.7 Counting Sort 72
2.1.8 Radix Sort 73
2.1.9 Bucket Sort 74
2.2 Selection 74
2.2.1 Maximum and Minimum 74
2.2.2 Expected Selection 76
2.2.3 Worst-case Linear Selection 76
2.3 Exercises & Solutions 77
Chapter 3Data Structures 135
3.1 Elementary Data Structures 135
3.1.1 Stacks and Queues 135
3.1.2 Linked Lists 136
3.2 Dynamic Sets and Searching 137
3.2.1 Hash Tables 137
3.2.2 Binary Search Trees 139
3.2.3 Red-black Trees 142
3.2.4 Augmenting Data Structures 144
3.3 Exercises & Solutions 145
Chapter 4Advanced Data Structures 185
4.1 B-Trees 185
4.1.1 Searching a B-tree 185
4.1.2 Creating a B-tree 186
4.2 Binomial Heaps 188
4.2.1 Finding The Minimum Key 188
4.2.2 Uniting Two Binomial Heaps 189
4.3 Fibonacci Heaps 191
4.3.1 Inserting a Node 191
4.3.2 Uniting Two Fibonacci Heaps 192
4.3.3 Extracting a Minimum Node 192
4.4 Data Structures for Disjoint Sets 195
4.5 Exercises & Solutions 196
Chapter 5Advanced Design andAnalysis Techniques 216
5.1 Divide-and-Conquer 216
5.1.1 Maximum and Minimum 216
5.1.2 Integer Multiplication 217
5.1.3 Strassen Matrix Multiplication 218
5.2 Dynamic Programming 219
5.2.1 String Reconstruction Problem 219
5.2.2 All Pairs Shortest Paths 221
5.2.3 Traveling Salesman Problems 222
5.3 Greedy Algorithms 223
5.3.1 Horn Formula 223
5.3.2 Huffman Coding 224
5.3.3 The Set Cover Problem 227
5.4 Amortized Analysis 228
5.4.1 The Aggregate Method 228
5.4.2 The Accounting Method 229
5.4.3 The Potential Method 230
5.4.4 Incrementing and Decrementing 231
5.5 Exercises & Solutions 233
Chapter 6Graph Algorithms 306
6.1 Elementary Graph Algorithms 307
6.1.1 Data Structures for Graphs 307
6.1.2 Depth-first Search 308
6.1.3 Breadth-first Search 309
6.1.4 Topological Sort 310
6.1.5 Strongly Connected Components 311
6.2 Minimum Spanning Trees 311
6.2.1 Boruvka’s Algorithm 312
6.2.2 Jarnik’s Algorithm 314
6.2.3 Prim’s Algorithm 315
6.2.4 Kruskal’s Algorithm 315
6.3 Single-Source Shortest Paths 316
6.3.1 Bellman-Ford Algorithm 316
6.3.2 SSSP in DAG 317
6.3.3 Dijkstra’s Algorithm 318
6.4 All-Pairs Shortest Paths 318
6.4.1 Johnson’s Algorithm 319
6.4.2 Dynamic Programmig 320
6.4.3 Divide-and-Conquer 321
6.4.4 Shortest Path and Matrix Multiplication 322
6.4.5 Floyd-Warshall’s Algorithm 323
6.5 Exercises & Solutions 324
Bibliography 384
版权页 2
Foreword 3
Preface 4
Contents 6
Chapter 1Mathematical Foundation 9
1.1 Growth of Functions 9
1.1.1 O-notation (Big-O) 9
1.1.2 -notation (Big-Omega) 10
1.1.3 Θ-notation (Big-Theta) 11
1.2 Recurrences 12
1.2.1 Substitution Method 12
1.2.2 Iteration Method 13
1.2.3 Recursion-tree Method 14
1.2.4 Master Method 15
1.2.5 Other Recurrences 15
1.3 Exercises & Solutions 15
Chapter 2Sorting and Selection 65
2.1 Sorting 65
2.1.1 Insertion Sort 65
2.1.2 Selection Sort 66
2.1.3 Mergesort 67
2.1.4 Heapsort 68
2.1.5 Priority Queue 69
2.1.6 Quicksort 71
2.1.7 Counting Sort 72
2.1.8 Radix Sort 73
2.1.9 Bucket Sort 74
2.2 Selection 74
2.2.1 Maximum and Minimum 74
2.2.2 Expected Selection 76
2.2.3 Worst-case Linear Selection 76
2.3 Exercises & Solutions 77
Chapter 3Data Structures 135
3.1 Elementary Data Structures 135
3.1.1 Stacks and Queues 135
3.1.2 Linked Lists 136
3.2 Dynamic Sets and Searching 137
3.2.1 Hash Tables 137
3.2.2 Binary Search Trees 139
3.2.3 Red-black Trees 142
3.2.4 Augmenting Data Structures 144
3.3 Exercises & Solutions 145
Chapter 4Advanced Data Structures 185
4.1 B-Trees 185
4.1.1 Searching a B-tree 185
4.1.2 Creating a B-tree 186
4.2 Binomial Heaps 188
4.2.1 Finding The Minimum Key 188
4.2.2 Uniting Two Binomial Heaps 189
4.3 Fibonacci Heaps 191
4.3.1 Inserting a Node 191
4.3.2 Uniting Two Fibonacci Heaps 192
4.3.3 Extracting a Minimum Node 192
4.4 Data Structures for Disjoint Sets 195
4.5 Exercises & Solutions 196
Chapter 5Advanced Design andAnalysis Techniques 216
5.1 Divide-and-Conquer 216
5.1.1 Maximum and Minimum 216
5.1.2 Integer Multiplication 217
5.1.3 Strassen Matrix Multiplication 218
5.2 Dynamic Programming 219
5.2.1 String Reconstruction Problem 219
5.2.2 All Pairs Shortest Paths 221
5.2.3 Traveling Salesman Problems 222
5.3 Greedy Algorithms 223
5.3.1 Horn Formula 223
5.3.2 Huffman Coding 224
5.3.3 The Set Cover Problem 227
5.4 Amortized Analysis 228
5.4.1 The Aggregate Method 228
5.4.2 The Accounting Method 229
5.4.3 The Potential Method 230
5.4.4 Incrementing and Decrementing 231
5.5 Exercises & Solutions 233
Chapter 6Graph Algorithms 306
6.1 Elementary Graph Algorithms 307
6.1.1 Data Structures for Graphs 307
6.1.2 Depth-first Search 308
6.1.3 Breadth-first Search 309
6.1.4 Topological Sort 310
6.1.5 Strongly Connected Components 311
6.2 Minimum Spanning Trees 311
6.2.1 Boruvka’s Algorithm 312
6.2.2 Jarnik’s Algorithm 314
6.2.3 Prim’s Algorithm 315
6.2.4 Kruskal’s Algorithm 315
6.3 Single-Source Shortest Paths 316
6.3.1 Bellman-Ford Algorithm 316
6.3.2 SSSP in DAG 317
6.3.3 Dijkstra’s Algorithm 318
6.4 All-Pairs Shortest Paths 318
6.4.1 Johnson’s Algorithm 319
6.4.2 Dynamic Programmig 320
6.4.3 Divide-and-Conquer 321
6.4.4 Shortest Path and Matrix Multiplication 322
6.4.5 Floyd-Warshall’s Algorithm 323
6.5 Exercises & Solutions 324
Bibliography 384
Exercises & solutions on algorithms = 算法题解 /
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
