Computer Algorithm Design and Analysis 5th Edition (Wang Xiaodong)

\"Design and Analysis of Computer Algorithms (5th Edition)\" has 9 chapters, as follows: Chapter 1 introduces the basic concepts of algorithms, and explains the computational complexity of algorithms and the description of algorithms. Then the contents of Chapters 2 to 9 are organized around the basic design strategies commonly used in algorithm design. Chapter 2 introduces recursion and divide-and-conquer strategies. Chapter 3 introduces dynamic programming algorithms, and uses specific examples to explain the design ideas, applicability and design points of dynamic programming algorithms. Chapter 4 introduces greedy algorithms, which are also an algorithm design strategy, and they have a certain connection with the design ideas of dynamic programming algorithms. Chapters 5 and 6 introduce backtracking and branch-and-bound methods respectively. The algorithms introduced in these two chapters are suitable for dealing with difficult problems. Chapter 7 introduces randomized algorithms, which provide solutions to difficult problems. Chapter 8 introduces linear programming and network flow algorithms. Many practical application problems can be transformed into linear programming and network flow problems, and can be effectively solved using the algorithms in Chapter 8. Chapter 9 introduces algorithms for strings and sequences that are used in big data and artificial intelligence. Contents Chapter 1 Algorithm Overview 1 1.1 Algorithms and Programs 1 1.2 Algorithm Complexity Analysis 1 1.3 NP-Completeness Theory 4 Algorithm Analysis Questions 1 7 Algorithm Implementation Questions 1 7 Chapter 2 Recursion and Divide and Conquer Strategy 11 2.1 The concept of recursion 11 2.2 The basic idea of ​​divide and conquer 16 2.3 Binary Search Technology 17 2.4 Multiplication of Large Integers 18 2.5 Strassen Matrix Multiplication 19 2.6 Board Covering 20 2.7 Merge Sort 22 2.8 Quick Sort 24 2.9 Linear Time Selection 26 2.10 The Closest Pair Problem 29 2.11 Round Robin Schedule 35 Algorithm Analysis Questions 2 36 Algorithm Implementation Questions 2 40 Chapter 3 Dynamic Programming 46 3.1 Matrix Multiplication Problem 47 3.2 Basic Elements of Dynamic Programming Algorithms 51 3.3 3.5 The Longest Common Subsequence 54 3.6 The Largest Subsegment Sum 57 3.7 The Optimal Triangulation of Convex Polygons 62 3.8 Polygonal Games 65 3.9 Image Compression 68 3.10 Circuit Wiring 70 3.11 Optimal Binary Search Tree 79 Algorithm Analysis Questions 3 81 Algorithm Implementation Questions 3 82 Chapter 4 Greedy Algorithms 95 4.1 Activity Scheduling Problem 95 4.2 Basic Elements of Greedy Algorithms 98 4.3 Optimal Loading 100 4.4 Huffman Coding 101 4.5 Single-Source Shortest Path 105 4.6 Minimum Spanning Tree 108 4.7 Multi-Machine Scheduling Problem 111 Algorithm Analysis Questions 4 113 Algorithm Implementation Questions 4 113 Chapter 5 Backtracking Methods 120 5.1 Backtracking Algorithm Framework 120 5.2 5.1 The Basic Idea of ​​the Branch and Bound Algorithm 167 6.2 The Single-Source Shortest Path Problem 170 6.3 The Loading Problem 172 6.4 The Routing Problem 178 6.5 The 0-1 Knapsack Problem 181 6.6 The Maximum Clique Problem 185 6.7 The Graph Coloring Problem 186 5.8 The m-Coloring Problem 187 5.9 The Traveling Salesman Problem 188 5.10 The Circle Arrangement Problem 190 5.11 The Circuit Board Arrangement Problem 191 5.12 The Continuous Postage Problem 193 5.13 The Efficiency Analysis of the Backtracking Method 195 Algorithm Analysis Problem 5 197 Algorithm Implementation Problem 5 198 Chapter 6 Branch and Bound Algorithm 111 6.1 The Basic Idea of ​​the Branch and Bound Algorithm 111 6.2 The Single-Source Shortest Path Problem 113 6.3 The Loading Problem 114 6.4 The Routing Problem 115 6.5 The 0-1 Knapsack Problem 116 6.6 The Maximum Clique Problem 118 Implementation Problem 7 239 Chapter 8 Linear Programming and Network Flow 243 8.1 Linear Programming Problem and Simplex Algorithm 243 8.2 Maximum Network Flow Problem 256 8.3 Minimum Cost Flow Problem 274 Algorithm Analysis Problem 8 292 Algorithm Implementation Problem 8 293 Chapter 9 Algorithms for Strings and Sequences 306 9.1 Substring Search Algorithm 306 9.2 Suffix Array and Longest Common String 318 9.3 Sequence Comparison Algorithms 328 Algorithm Analysis Questions 9 336 Algorithm Implementation Questions 9 338 Appendix A C++ Overview 342 References 349