Design and analysis of algorithms

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