The Algorithm Design ManualPDF电子书下载

Ⅰ Practical Algorithm Design 1

1 Introduction to Algorithm Design 3

1.1 Robot Tour Optimization 5

1.2 Selecting the Right Jobs 9

1.3 Reasoning about Correctness 11

1.4 Modeling the Problem 19

1.5 About the War Stories 22

1.6 War Story: Psychic Modeling 23

1.7 Exercises 27

2 Algorithm Analysis 31

2.1 The RAM Model of Computation 31

2.2 The Big Oh Notation 34

2.3 Growth Rates and Dominance Relations 37

2.4 Working with the Big Oh 40

2.5 Reasoning About Efficiency 41

2.6 Logarithms and Their Applications 46

2.7 Properties of Logarithms 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

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 of Moore’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

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 Search Methods 247

7.6 War Story: Only it is Not a Radio 260

7.7 War Story: Annealing Arrays 263

7.8 Other Heuristic Search Methods 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 Satistiability 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

Ⅱ The Hitchhiker’s Guide to Algorithms 361

11 A Catalog of Algorithmic Problems 363

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

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

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