دانلود کتاب Design and Analysis of Algorithms

فهرست مطالب :

Preface ......Page 3
Table of Contents ......Page 4
1: Overview of Course ......Page 8
2: Sply Trees ......Page 10
3: Amortized Time for Sply Trees ......Page 13
4: Maintaining Disjoint Sets ......Page 17
5: Binomial heaps ......Page 21
6: F-heap ......Page 25
7: Minimum Spanning Trees ......Page 30
8: Fredman-Tarjan MST Algorithm ......Page 32
9: Branching Problem ......Page 34
10: Light Approximate Shortest Path Trees ......Page 36
11: Matchings ......Page 40
12: Hopcroft-Karp Matching Algorithm ......Page 43
13: Two Processor Scheduling ......Page 46
14: Assignment Problem ......Page 48
15: Network Flow—Maximum Flow Problem ......Page 51
16: The Max Flow Problem ......Page 56
17: An O(n³) Max-Flow Algorithm ......Page 58
18: Vertex Covers and Network Flow ......Page 60
20: Planar Graphs ......Page 65
21: Graph Coloring ......Page 68
22: Graph Minor Theorem and other CS Collectibles ......Page 69
23: The Min Cost Flow Problem ......Page 72
24: Shortest Path based Algorithm for Min Cost Flows ......Page 74
25: NP-completeness......Page 76
26: NP-completeness......Page 78
27: NP-completeness ......Page 80
28: More on NP-completeness ......Page 81
29: 2 Satisfiability ......Page 83
30: Linear Programming ......Page 84
31: Vertex Cover ......Page 89
32: Weighted Vertex Cover ......Page 90
33: A (2 - f(n)) Approximation Algorithm for the Vertex Cover Problem ......Page 94
34: Nemhauser-Trotter Theorem ......Page 97
35: Approximation Algorithms: Set Cover......Page 98
36: Approximation Algorithms: Set Cover and Max Coverage......Page 102
37: Approximation Algorithms: K-Centers ......Page 104
38: Bin Packing ......Page 106
39: Multi-cost Minimum Spanning Trees ......Page 110
40: Set and Vertex Cover Approximations: Randomized Algorithms ......Page 113
41: Steiner Tree Problem ......Page 116
42: Traveling Salesperson and Chinese Postman Problem ......Page 121
43: Vehicle Routing Problems: Stacker Crane......Page 126
45: Unit Capacity Problem (1-delivery TSP) ......Page 129
46: K-capacity Problem ......Page 130
47: Unbounded Capacity Problem ......Page 133
48: Lower Bounds on Approximations ......Page 134
49: Lower Bounds on Approximations (contd) ......Page 139
50: Linear Programming: The Use of Duality ......Page 142
51: Using duality to analyze (and design) approximation algorithms ......Page 147
52: A General Approximation Technique for Constrained Forest Problems ......Page 152
53: On Lİne vs. Off Line: A Measure for Quality Evaluation ......Page 157
References ......Page 160