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