The Algorithm Design Manual下载

weixin_39821526 2020-11-27 04:00:48

his expanded and updated second edition of a classic bestseller continues to take the “mystery” out of designing and analyzing algorithms and their efficacy and efficiency. Expanding on the highly successful formula of the first edition, the book now serves as the primary textbook of choice for any
相关下载链接：//download.csdn.net/download/iconhacker/3350776?utm_source=bbsseo

...全文

10 回复打赏收藏转发到动态举报

写回复

回复

切换为时间正序

请发表友善的回复…

发表回复

I Practical Algorithm Design 1 Introduction to Algorithm Design 1.1 Robot Tour Optimization 1.2 Selecting the Right Jobs 1.3 Reasoning about Correctness 1.4 Modeling the Problem 1.5 About theWar Stories 1.6 War Story: PsychicModeling 1.7 Exercises 2 Algorithm Analysis 2.1 The RAM Model of Computation 2.2 The Big Oh Notation 2.3 Growth Rates and Dominance Relations 2.4 Working with the Big Oh 2.5 Reasoning About Efficiency 2.6 Logarithms and Their Applications 2.7 Properties of Logarithms 2.8 War Story: Mystery of the Pyramids 2.9 Advanced Analysis (*) 2.10 Exercises 3 Data Structures 3.1 Contiguous vs. Linked Data Structures 3.2 Stacks and Queues 3.3 Dictionaries 3.4 Binary Search Trees 3.5 Priority Queues 3.6 War Story: Stripping Triangulations 3.7 Hashing and Strings 3.8 Specialized Data Structures 3.9 War Story: String ’em Up 3.10 Exercises 4 Sorting and Searching 4.1 Applications of Sorting 4.2 Pragmatics of Sorting 4.3 Heapsort: Fast Sorting via Data Structures 4.4 War Story: Give me a Ticket on an Airplane 4.5 Mergesort: Sorting by Divide-and-Conquer 4.6 Quicksort: Sorting by Randomization 4.7 Distribution Sort: Sorting via Bucketing 4.8 War Story: Skiena for the Defense 4.9 Binary Search and Related Algorithms 4.10 Divide-and-Conquer 4.11 Exercises 5 Graph Traversal 5.1 Flavors of Graphs 5.2 Data Structures for Graphs 5.3 War Story: I was a Victim ofMoore’s Law 5.4 War Story: Getting the Graph 5.5 Traversing a Graph 5.6 Breadth-First Search 5.7 Applications of Breadth-First Search 5.8 Depth-First Search 5.9 Applications of Depth-First Search 5.10 Depth-First Search on Directed Graphs 5.11 Exercises 6 Weighted Graph Algorithms 6.1 Minimum Spanning Trees 6.2 War Story: Nothing but Nets 6.3 Shortest Paths 6.4 War Story: Dialing for Documents 6.5 Network Flows and Bipartite Matching 6.6 Design Graphs, Not Algorithms 6.7 Exercises 7 Combinatorial Search and Heuristic Methods 7.1 Backtracking 7.2 Search Pruning 7.3 Sudoku 7.4 War Story: Covering Chessboards 7.5 Heuristic SearchMethods 7.6 War Story: Only it is Not a Radio 7.7 War Story: Annealing Arrays 7.8 Other Heuristic SearchMethods 7.9 Parallel Algorithms 7.10 War Story: Going Nowhere Fast 7.11 Exercises 8 Dynamic Programming 8.1 Caching vs. Computation 8.2 Approximate String Matching 8.3 Longest Increasing Sequence 8.4 War Story: Evolution of the Lobster 8.5 The Partition Problem 8.6 Parsing Context-Free Grammars 8.7 Limitations of Dynamic Programming: TSP 8.8 War Story: What’s Past is Prolog 8.9 War Story: Text Compression for Bar Codes 8.10 Exercises 9 Intractable Problems and Approximation Algorithms 9.1 Problems and Reductions 9.2 Reductions for Algorithms 9.3 Elementary Hardness Reductions 9.4 Satisfiability 9.5 Creative Reductions 9.6 The Art of Proving Hardness 9.7 War Story: Hard Against the Clock 9.8 War Story: And Then I Failed 9.9 P vs. NP 9.10 Dealing with NP-complete Problems 9.11 Exercises 10 How to Design Algorithms II The Hitchhiker’s Guide to Algorithms 11 A Catalog of Algorithmic Problems 12 Data Structures 12.1 Dictionaries 12.2 Priority Queues 12.3 Suffix Trees and Arrays 12.4 Graph Data Structures 12.5 Set Data Structures 12.6 Kd-Trees 13 Numerical Problems 13.1 Solving Linear Equations 13.2 Bandwidth Reduction 13.3 Matrix Multiplication 13.4 Determinants and Permanents 13.5 Constrained and Unconstrained Optimization 13.6 Linear Programming 13.7 Random Number Generation 13.8 Factoring and Primality Testing 13.9 Arbitrary-Precision Arithmetic 13.10 Knapsack Problem 13.11 Discrete Fourier Transform 14 Combinatorial Problems 14.1 Sorting 14.2 Searching 14.3 Median and Selection 14.4 Generating Permutations 14.5 Generating Subsets 14.6 Generating Partitions 14.7 Generating Graphs 14.8 Calendrical Calculations 14.9 Job Scheduling 14.10 Satisfiability 15 Graph Problems: Polynomial-Time 15.1 Connected Components 15.2 Topological Sorting 15.3 Minimum Spanning Tree 15.4 Shortest Path 15.5 Transitive Closure and Reduction 15.6 Matching 15.7 Eulerian Cycle/Chinese Postman 15.8 Edge and Vertex Connectivity 15.9 Network Flow 15.10 Drawing Graphs Nicely 15.11 Drawing Trees 15.12 Planarity Detection and Embedding 16 Graph Problems: Hard Problems 16.1 Clique 16.2 Independent Set 16.3 Vertex Cover 16.4 Traveling Salesman Problem 16.5 Hamiltonian Cycle 16.6 Graph Partition 16.7 Vertex Coloring 16.8 Edge Coloring 16.9 Graph Isomorphism 16.10 Steiner Tree 16.11 Feedback Edge/Vertex Set 17 Computational Geometry 562 17.1 Robust Geometric Primitives 17.2 Convex Hull 17.3 Triangulation 17.4 Voronoi Diagrams 17.5 Nearest Neighbor Search 17.6 Range Search 17.7 Point Location 17.8 Intersection Detection 17.9 Bin Packing 17.10 Medial-Axis Transform 17.11 Polygon Partitioning 17.12 Simplifying Polygons 17.13 Shape Similarity 17.14 Motion Planning 17.15 Maintaining Line Arrangements 17.16 Minkowski Sum 18 Set and String Problems 18.1 Set Cover 18.2 Set Packing 18.3 String Matching 18.4 Approximate String Matching 18.5 Text Compression 18.6 Cryptography 18.7 Finite State Machine Minimization 18.8 Longest Common Substring/Subsequence 18.9 Shortest Common Superstring 19 Algorithmic Resources 19.1 Software Systems 19.2 Data Sources 19.3 Online Bibliographic Resources 19.4 Professional Consulting Services Bibliography Index

英文第二版目录 . . . . . . . . . . . . . . . . . . . . . . . 50 2.8 War Story: Mystery of the Pyramids . . . . . . . . . . . . . . . . 51 2.9 Advanced Analysis (*) . . . . . . . . . . . . . . . . . . . . . . . . 54 2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3 Data Structures 65 3.1 Contiguous vs. Linked Data Structures . . . . . . . . . . . . . . . 66 xii CONTENTS 3.2 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.3 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.4 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.5 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.6 War Story: Stripping Triangulations . . . . . . . . . . . . . . . . 85 3.7 Hashing and Strings . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.8 Specialized Data Structures . . . . . . . . . . . . . . . . . . . . . 93 3.9 War Story: String ’em Up . . . . . . . . . . . . . . . . . . . . . . 94 3.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4 Sorting and Searching 103 4.1 Applications of Sorting . . . . . . . . . . . . . . . . . . . . . . . . 104 4.2 Pragmatics of Sorting . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.3 Heapsort: Fast Sorting via Data Structures . . . . . . . . . . . . 108 4.4 War Story: Give me a Ticket on an Airplane . . . . . . . . . . . 118 4.5 Mergesort: Sorting by Divide-and-Conquer . . . . . . . . . . . . 120 4.6 Quicksort: Sorting by Randomization . . . . . . . . . . . . . . . 123 4.7 Distribution Sort: Sorting via Bucketing . . . . . . . . . . . . . . 129 4.8 War Story: Skiena for the Defense . . . . . . . . . . . . . . . . . 131 4.9 Binary Search and Related Algorithms . . . . . . . . . . . . . . . 132 4.10 Divide-and-Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5 Graph Traversal 145 5.1 Flavors of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.2 Data Structures for Graphs . . . . . . . . . . . . . . . . . . . . . 151 5.3 War Story: I was a Victim ofMoore’s Law . . . . . . . . . . . . 155 5.4 War Story: Getting the Graph . . . . . . . . . . . . . . . . . . . . 158 5.5 Traversing a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 161 5.6 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . 162 5.7 Applications of Breadth-First Search . . . . . . . . . . . . . . . . 166 5.8 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . 169 5.9 Applications of Depth-First Search . . . . . . . . . . . . . . . . . 172 5.10 Depth-First Search on Directed Graphs . . . . . . . . . . . . . . 178 5.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 6 Weighted Graph Algorithms 191 6.1 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . 192 6.2 War Story: Nothing but Nets . . . . . . . . . . . . . . . . . . . . 202 6.3 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6.4 War Story: Dialing for Documents . . . . . . . . . . . . . . . . . 212 6.5 Network Flows and Bipartite Matching . . . . . . . . . . . . . . 217 6.6 Design Graphs, Not Algorithms . . . . . . . . . . . . . . . . . . . 222 6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 CONTENTS xiii 7 Combinatorial Search and Heuristic Methods 230 7.1 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.2 Search Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 7.3 Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 7.4 War Story: Covering Chessboards . . . . . . . . . . . . . . . . . . 244 7.5 Heuristic SearchMethods . . . . . . . . . . . . . . . . . . . . . . 247 7.6 War Story: Only it is Not a Radio . . . . . . . . . . . . . . . . . 260 7.7 War Story: Annealing Arrays . . . . . . . . . . . . . . . . . . . . 263 7.8 Other Heuristic SearchMethods . . . . . . . . . . . . . . . . . . 266 7.9 Parallel Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 267 7.10 War Story: Going Nowhere Fast . . . . . . . . . . . . . . . . . . . 268 7.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 8 Dynamic Programming 273 8.1 Caching vs. Computation . . . . . . . . . . . . . . . . . . . . . . 274 8.2 Approximate String Matching . . . . . . . . . . . . . . . . . . . . 280 8.3 Longest Increasing Sequence . . . . . . . . . . . . . . . . . . . . . 289 8.4 War Story: Evolution of the Lobster . . . . . . . . . . . . . . . . 291 8.5 The Partition Problem . . . . . . . . . . . . . . . . . . . . . . . . 294 8.6 Parsing Context-Free Grammars . . . . . . . . . . . . . . . . . . 298 8.7 Limitations of Dynamic Programming: TSP . . . . . . . . . . . . 301 8.8 War Story: What’s Past is Prolog . . . . . . . . . . . . . . . . . . 304 8.9 War Story: Text Compression for Bar Codes . . . . . . . . . . . 307 8.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 9 Intractable Problems and Approximation Algorithms 316 9.1 Problems and Reductions . . . . . . . . . . . . . . . . . . . . . . 317 9.2 Reductions for Algorithms . . . . . . . . . . . . . . . . . . . . . . 319 9.3 Elementary Hardness Reductions . . . . . . . . . . . . . . . . . . 323 9.4 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 9.5 Creative Reductions . . . . . . . . . . . . . . . . . . . . . . . . . 330 9.6 The Art of Proving Hardness . . . . . . . . . . . . . . . . . . . . 334 9.7 War Story: Hard Against the Clock . . . . . . . . . . . . . . . . . 337 9.8 War Story: And Then I Failed . . . . . . . . . . . . . . . . . . . . 339 9.9 P vs. NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 9.10 Dealing with NP-complete Problems . . . . . . . . . . . . . . . . 344 9.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 10 How to Design Algorithms 356 II The Hitchhiker’s Guide to Algorithms 361 11 A Catalog of Algorithmic Problems 363 xiv CONTENTS 12 Data Structures 366 12.1 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 12.2 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 12.3 Suffix Trees and Arrays . . . . . . . . . . . . . . . . . . . . . . . . 377 12.4 Graph Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 381 12.5 Set Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . 385 12.6 Kd-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 13 Numerical Problems 393 13.1 Solving Linear Equations . . . . . . . . . . . . . . . . . . . . . . . 395 13.2 Bandwidth Reduction . . . . . . . . . . . . . . . . . . . . . . . . 398 13.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . 401 13.4 Determinants and Permanents . . . . . . . . . . . . . . . . . . . . 404 13.5 Constrained and Unconstrained Optimization . . . . . . . . . . . 407 13.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 411 13.7 Random Number Generation . . . . . . . . . . . . . . . . . . . . 415 13.8 Factoring and Primality Testing . . . . . . . . . . . . . . . . . . . 420 13.9 Arbitrary-Precision Arithmetic . . . . . . . . . . . . . . . . . . . 423 13.10 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 427 13.11 Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . 431 14 Combinatorial Problems 434 14.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 14.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 14.3 Median and Selection . . . . . . . . . . . . . . . . . . . . . . . . . 445 14.4 Generating Permutations . . . . . . . . . . . . . . . . . . . . . . . 448 14.5 Generating Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . 452 14.6 Generating Partitions . . . . . . . . . . . . . . . . . . . . . . . . . 456 14.7 Generating Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 460 14.8 Calendrical Calculations . . . . . . . . . . . . . . . . . . . . . . . 465 14.9 Job Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 14.10 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 15 Graph Problems: Polynomial-Time 475 15.1 Connected Components . . . . . . . . . . . . . . . . . . . . . . . 477 15.2 Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 481 15.3 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . 484 15.4 Shortest Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 15.5 Transitive Closure and Reduction . . . . . . . . . . . . . . . . . . 495 15.6 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 15.7 Eulerian Cycle/Chinese Postman . . . . . . . . . . . . . . . . . . 502 15.8 Edge and Vertex Connectivity . . . . . . . . . . . . . . . . . . . . 505 15.9 Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 15.10 Drawing Graphs Nicely . . . . . . . . . . . . . . . . . . . . . . . . 513 CONTENTS xv 15.11 Drawing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 15.12 Planarity Detection and Embedding . . . . . . . . . . . . . . . . 520 16 Graph Problems: Hard Problems 523 16.1 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 16.2 Independent Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 16.3 Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 16.4 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . 533 16.5 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 538 16.6 Graph Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 16.7 Vertex Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 16.8 Edge Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548 16.9 Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . 550 16.10 Steiner Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555 16.11 Feedback Edge/Vertex Set . . . . . . . . . . . . . . . . . . . . . . 559 17 Computational Geometry 562 17.1 Robust Geometric Primitives . . . . . . . . . . . . . . . . . . . . 564 17.2 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 17.3 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572 17.4 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 17.5 Nearest Neighbor Search . . . . . . . . . . . . . . . . . . . . . . . 580 17.6 Range Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 17.7 Point Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 17.8 Intersection Detection . . . . . . . . . . . . . . . . . . . . . . . . 591 17.9 Bin Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595 17.10 Medial-Axis Transform . . . . . . . . . . . . . . . . . . . . . . . . 598 17.11 Polygon Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 601 17.12 Simplifying Polygons . . . . . . . . . . . . . . . . . . . . . . . . . 604 17.13 Shape Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 17.14 Motion Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 610 17.15 Maintaining Line Arrangements . . . . . . . . . . . . . . . . . . . 614 17.16 Minkowski Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617 18 Set and String Problems 620 18.1 Set Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621 18.2 Set Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 18.3 String Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 18.4 Approximate String Matching . . . . . . . . . . . . . . . . . . . . 631 18.5 Text Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . 637 18.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641 18.7 Finite State Machine Minimization . . . . . . . . . . . . . . . . . 646 18.8 Longest Common Substring/Subsequence . . . . . . . . . . . . . 650 18.9 Shortest Common Superstring . . . . . . . . . . . . . . . . . . . . 654 xvi CONTENTS 19 Algorithmic Resources 657 19.1 Software Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 657 19.2 Data Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 19.3 Online Bibliographic Resources . . . . . . . . . . . . . . . . . . . 663 19.4 Professional Consulting Services . . . . . . . . . . . . . . . . . . . 664 Bibliography 665 Index 709

经典算法，学习算法的宝书 The Algorithm Design Manual 2ed

The Algorithm Design Manual(2nd Ed.)源代码，包含Programming Challenges: The Programming Contest Training Manual源代码

下载资源悬赏专区

13,655

社区成员

12,654,824

社区内容

发帖

与我相关

我的任务

其他技术论坛（原bbs）

社区管理员

加入社区

近7日
近30日
至今

加载中

查看更多榜单

社区公告

暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章