算法导论 英文版PDF|Epub|txt|kindle电子书版本网盘下载

算法导论 英文版PDF格式电子书版下载

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

Ⅰ Foundations3

Introduction3

1 The Role of Algorithms in Computing5

1.1 Algorithms5

1.2 Algorithms as a technology10

2 Getting Started15

2.1 Insertion sort15

2.2 Analyzing algorithms21

2.3 Designing algorithms27

3 Growth of Functions41

3.1 Asymptotic notation41

3.2 Standard notations and common functions51

4 Recurrences62

4.1 The substitution method63

4.2 The recursion-tree method67

4.3 The master method73

4.4 Proof of the master theorem76

5 Probabilistic Analysis and Randomized Algorithms91

5.1 The hiring Problem91

5.2 Indicator random variables94

5.3 Randomized algorithms99

5.4 Probabilistic analysis and further uses of indicator random variables106

Ⅱ Sorting and Order Statistics123

Introduction123

6 Heapsort127

6.1 Heaps127

6.2 Maintaining the heap property130

6.3 Building a heap132

6.4 The heapsort algorithm135

6.5 Priority queues138

7 Quicksort145

7.1 Description of quicksort145

7.2 Performance of quicksort149

7.3 A randomized version of quicksort153

7.4 Analysis of quicksort155

8 Sorting in Linear Time165

8.1 Lower bounds for sorting165

8.2 Counting sort168

8.3 Radix sort170

8.4 Bucket sort174

9 Medians and Order Statistics183

9.1 Minimum and maximum184

9.2 Selection in expected linear time185

9.3 Selection in Worst-case linear time189

Ⅲ Data Structures197

Introduction197

10 Elementary Data Structures200

10.1 Stacks and queues200

10.2 Linked lists204

10.3 Implementing pointers and objects209

10.4 Represeting rooted trees214

11 Hash Tables221

11.1 Direct-address tables222

11.2 Hash tables224

11.3 Hash functions229

11.4 Open addressing237

11.5 Perfect hashing245

12 Binary Search Trees253

12.1 What is a binary search tree?253

12.2 Querying a binary search tree256

12.3 Insertion and deletion261

12.4 Randomly built binary search trees265

13 Red-Black Trees273

13.1 Properties of red-black trees273

13.2 Rotations277

13.3 Insertion280

13.4 Deletion288

14 Augmenting Data Structures302

14.1 Dynamic order statistics302

14.2 How to augment a data structure308

14.3 Interval trees311

Ⅳ Advanced Design and Analysis Techniques321

Introduction321

15 Dynamic Programming323

15.1 Assembly-line scheduling324

15.2 Matrix-chain multiplication331

15.3 Elements of dynamic programming339

15.4 Longest common subsequence350

15.5 Optimal binary search trees356

16 Greedy Algorithms370

16.1 An activity-Selection Problem371

16.2 Elements of the greedy Strategy379

16.3 Huffman codes385

16.4 Theoretical foundations for greedy methods393

16.5 A task-scheduling problem399

17 Amortized Analysis405

17.1 Aggregate analysis406

17.2 The accounting method410

17.3 The Potential method412

17.4 Dynamic tables416

Ⅴ Advanced Data Structures431

Introduction431

18 B-Trees434

18.1 Definition of B-trees438

18.2 Basic operations on B-trees441

18.3 Deleting a key form a B-tree449

19 Binomial Heaps445

19.1 Binomial trees and binomial heaps457

19.2 Operations on binomial heaps461

20 Fibonacci Heaps476

20.1 Structure of Fibonacci heaps477

20.2 Mergeable-heap Operations479

20.3 Decreasing a key and deleting a node489

20.4 Bounding the maximum degree493

21 Data Structures for Disjoint Sets498

21.1 Disjoint-set Operations498

21.2 Linked-list representation of disjoint sets501

21.3 Disjoint-set forests505

21.4 Analysis of union by rank with path compression509

Ⅵ Graph Algorithms525

Introduction525

22 Elementary Graph Algorithms527

22.1 Representations of graphs527

22.2 Breadth-first search531

22.3 Depth-fist search540

22.4 Topological sort549

22.5 Strongly connected components552

23 Minimum Spanning Trees561

23.1 Growing a minimum spanning tree562

23.2 The algorithms of kruskal and prim567

24 Single-Source Shortest Paths580

24.1 The Bellman-Ford algorithm588

24.2 Single-source shortest paths in directed acyclic graphs592

24.3 Dijkstra s algorithm595

24.4 Difference constraints and shortest paths601

24.5 Proofs of shortest-paths properties607

25 All-Pairs Shortest Paths620

25.1 Shortest Paths and matrix multiplication622

25.2 The Floyed-Warshall algorithm629

25.3 Johnson s algorithm for sparse graphs636

26 Maximum Flow643

26.1 Flow networks644

26.2 The Ford-Fulkerson method651

26.3 Maximum bipartite matching664

26.4 Push-relabel algorithms669

26.5 The relabel-to-front algorithm681

Ⅶ Selected Topics701

Introduction701

27 Sorting Networks704

27.1 Comparison networks704

27.2 The zero-one Principle709

27.3 A bitonic sorting network712

27.4 A merging network716

27.5 A sorting network719

28 Matrix Operations725

28.1 Properties of matrices725

28.2 Strassen s algorithm for matrix multiplication735

28.3 Solving systems of linear equations742

28.4 Inverting matrices755

28.5 Symmetric positive-definite matrices and least-squares approximation760

29 Linear Programming770

29.1 Standard and slack forms777

29.2 Formulating problems as linear programs785

29.3 The simplex algorithm790

29.4 Duality804

29.5 The initial basic feasible solution811

30 Polynomials and the FFT822

30.1 Representation of polynomials824

30.2 The DFT and FFT830

30.3 Efficient FFT implementations839

31 Number-Theoretic Algorithms849

31.1 Elementary number-theoretic notions850

31.2 Greatest common divisor856

31.3 Modular arithmetic862

31.4 Solving modular linear equations869

31.5 The Chinese remainder theorem873

31.6 Powers of an element876

31.7 The RSA public-Key cryptosystem881

31.8 Primality testing887

31.9 Integer factorization896

32 String Matching906

32.1 The naive String-matching algorithm909

32.2 The Rabin-Karp algorithm911

32.3 String matching with finite automata916

32.4 The Knuth-Morris-Pratt algorithm923

33 Computational Geometry933

33.1 Line-segment properties934

33.2 Determining whether any pair of segments intersects940

33.3 Finding the convex hull947

33.4 Finding the closest pair of points957

34 NP-Completeness966

34.1 Polynomial time971

34.2 Polynomial-time verification979

34.3 NP-completeness and reducibility984

34.4 NP-completeness proofs995

34.5 NP-complete problems1003

35 Approximation Algorithms1022

35.1 The vertex-cover problem1024

35.2 The traveling-salesman problem1027

35.3 The set-covering problem1033

35.4 Randomization and linear programming1039

35.5 The subset-sum problem1043

Ⅷ Appendix: Mathematical Background1057

Introduction1057

A Summations1058

A.1 Summation formulas and Properties1058

A.2 Bounding summations1062

B Sets.Etc1070

B.1 Sets1070

B.2 Relations1075

B.3 Functions1077

B.4 Graphs1080

B.5 Trees1085

C Counting and Probability1094

C.1 Counting1094

C.2 Probability1100

C.3 Discrete random variables1106

C.4 The geometric and binomial distributions1112

C.5 The tails of the binomial distribution1118

Bibliography1127

Index1145