The Algorithm Design ManualPDF|Epub|txt|kindle电子书版本网盘下载

The Algorithm Design ManualPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Ⅰ Practical Algorithm Design1

1 Introduction to Algorithm Design3

1.1 Robot Tour Optimization5

1.2 Selecting the Right Jobs9

1.3 Reasoning about Correctness11

1.4 Modeling the Problem19

1.5 About the War Stories22

1.6 War Story: Psychic Modeling23

1.7 Exercises27

2 Algorithm Analysis31

2.1 The RAM Model of Computation31

2.2 The Big Oh Notation34

2.3 Growth Rates and Dominance Relations37

2.4 Working with the Big Oh40

2.5 Reasoning About Efficiency41

2.6 Logarithms and Their Applications46

2.7 Properties of Logarithms50

2.8 War Story: Mystery of the Pyramids51

2.9 Advanced Analysis（*）54

2.10 Exercises57

3 Data Structures65

3.1 Contiguous vs.Linked Data Structures66

3.2 Stacks and Queues71

3.3 Dictionaries72

3.4 Binary Search Trees77

3.5 Priority Queues83

3.6 War Story: Stripping Triangulations85

3.7 Hashing and Strings89

3.8 Specialized Data Structures93

3.9 War Story: String ’em Up94

3.10 Exercises98

4 Sorting and Searching103

4.1 Applications of Sorting104

4.2 Pragmatics of Sorting107

4.3 Heapsort: Fast Sorting via Data Structures108

4.4 War Story: Give me a Ticket on an Airplane118

4.5 Mergesort: Sorting by Divide-and-Conquer120

4.6 Quicksort: Sorting by Randomization123

4.7 Distribution Sort: Sorting via Bucketing129

4.8 War Story: Skiena for the Defense131

4.9 Binary Search and Related Algorithms132

4.10 Divide-and-Conquer135

4.11 Exercises139

5 Graph Traversal145

5.1 Flavors of Graphs146

5.2 Data Structures for Graphs151

5.3 War Story: I was a Victim of Moore’s Law155

5.4 War Story: Getting the Graph158

5.5 Traversing a Graph161

5.6 Breadth-First Search162

5.7 Applications of Breadth-First Search166

5.8 Depth-First Search169

5.9 Applications of Depth-First Search172

5.10 Depth-First Search on Directed Graphs178

5.11 Exercises184

6 Weighted Graph Algorithms191

6.1 Minimum Spanning Trees192

6.2 War Story: Nothing but Nets202

6.3 Shortest Paths205

6.4 War Story: Dialing for Documents212

6.5 Network Flows and Bipartite Matching217

6.6 Design Graphs, Not Algorithms222

6.7 Exercises225

7 Combinatorial Search and Heuristic Methods230

7.1 Backtracking231

7.2 Search Pruning238

7.3 Sudoku239

7.4 War Story: Covering Chessboards244

7.5 Heuristic Search Methods247

7.6 War Story: Only it is Not a Radio260

7.7 War Story: Annealing Arrays263

7.8 Other Heuristic Search Methods266

7.9 Parallel Algorithms267

7.10 War Story: Going Nowhere Fast268

7.11 Exercises270

8 Dynamic Programming273

8.1 Caching vs.Computation274

8.2 Approximate String Matching280

8.3 Longest Increasing Sequence289

8.4 War Story: Evolution of the Lobster291

8.5 The Partition Problem294

8.6 Parsing Context-Free Grammars298

8.7 Limitations of Dynamic Programming: TSP301

8.8 War Story: What’s Past is Prolog304

8.9 War Story: Text Compression for Bar Codes307

8.10 Exercises310

9 Intractable Problems and Approximation Algorithms316

9.1 Problems and Reductions317

9.2 Reductions for Algorithms319

9.3 Elementary Hardness Reductions323

9.4 Satistiability328

9.5 Creative Reductions330

9.6 The Art of Proving Hardness334

9.7 War Story: Hard Against the Clock337

9.8 War Story: And Then I Failed339

9.9 P vs.NP341

9.10 Dealing with NP-complete Problems344

9.11 Exercises350

10 How to Design Algorithms356

Ⅱ The Hitchhiker’s Guide to Algorithms361

11 A Catalog of Algorithmic Problems363

12 Data Structures366

12.1 Dictionaries367

12.2 Priority Queues373

12.3 Suffix Trees and Arrays377

12.4 Graph Data Structures381

12.5 Set Data Structures385

12.6 Kd-Trees389

13 Numerical Problems393

13.1 Solving Linear Equations395

13.2 Bandwidth Reduction398

13.3 Matrix Multiplication401

13.4 Determinants and Permanents404

13.5 Constrained and Unconstrained Optimization407

13.6 Linear Programming411

13.7 Random Number Generation415

13.8 Factoring and Primality Testing420

13.9 Arbitrary-Precision Arithmetic423

13.10 Knapsack Problem427

13.11 Discrete Fourier Transform431

14 Combinatorial Problems434

14.1 Sorting436

14.2 Searching441

14.3 Median and Selection445

14.4 Generating Permutations448

14.5 Generating Subsets452

14.6 Generating Partitions456

14.7 Generating Graphs460

14.8 Calendrical Calculations465

14.9 Job Scheduling468

14.10 Satisfiability472

15 Graph Problems: Polynomial-Time475

15.1 Connected Components477

15.2 Topological Sorting481

15.3 Minimum Spanning Tree484

15.4 Shortest Path489

15.5 Transitive Closure and Reduction495

15.6 Matching498

15.7 Eulerian Cycle/Chinese Postman502

15.8 Edge and Vertex Connectivity505

15.9 Network Flow509

15.10 Drawing Graphs Nicely513

15.11 Drawing Trees517

15.12 Planarity Detection and Embedding520

16 Graph Problems: Hard Problems523

16.1 Clique525

16.2 Independent Set528

16.3 Vertex Cover530

16.4 Traveling Salesman Problem533

16.5 Hamiltonian Cycle538

16.6 Graph Partition541

16.7 Vertex Coloring544

16.8 Edge Coloring548

16.9 Graph Isomorphism550

16.10 Steiner Tree555

16.11 Feedback Edge/Vertex Set559

17 Computational Geometry562

17.1 Robust Geometric Primitives564

17.2 Convex Hull568

17.3 Triangulation572

17.4 Voronoi Diagrams576

17.5 Nearest Neighbor Search580

17.6 Range Search584

17.7 Point Location587

17.8 Intersection Detection591

17.9 Bin Packing595

17.10 Medial-Axis Transform598

17.11 Polygon Partitioning601

17.12 Simplifying Polygons604

17.13 Shape Similarity607

17.14 Motion Planning610

17.15 Maintaining Line Arrangements614

17.16 Minkowski Sum617

18 Set and String Problems620

18.1 Set Cover621

18.2 Set Packing625

18.3 String Matching628

18.4 Approximate String Matching631

18.5 Text Compression637

18.6 Cryptography641

18.7 Finite State Machine Minimization646

18.8 Longest Common Substring/Subsequence650

18.9 Shortest Common Superstring654

19 Algorithmic Resources657

19.1 Software Systems657

19.2 Data Sources663

19.3 Online Bibliographic Resources663

19.4 Professional Consulting Services664

Bibliography665