CS614 : Advanced Algorithm
Instructor: Manoj Gupta
Timings: M W Th, 4 pm to 5 pm
30% : Assignments
60% : Viva/Exam
10% : Project
The tentative list of topics covered are as follows:
Approximation Algorithm
Randomized Algorithm
Exact algorithms
Parameterized Algorithms
| Topic | Slides | |
| Intro | 1 | |
| Expectation and Deviation | 2 | |
| Chernoff's Bound | 3 | |
| Probabilistic Method | 4 | |
| Examples of Randomized Algorithms | 6 | |
| Backward Analysis | 7 | |
| Strings | 8 | |
| Approximation Algorithm Intro | 9 | |
| Steiner Tree and TSP | 10 | |
| k-center | 11 | |
| LP | 12 | |
| LP Duality | 13 | |
| Dual Fitting | 14 | |
| Primal Dual | 15 | |
| Steiner Tree | 16 | |
| Assignment 1 |
| Assignment 2 |
| Assignment 3 |
| Assignment 4 |
| Assignment 5 |
Fast 2-Approximate All-Pairs Shortest Paths(Till page 17. The unweighted part)(Ashish Rawat)
New Algorithms for All Pairs Approximate Shortest Paths
Spanning Adjacency Oracles in Sublinear Time( Aslaliya Juhil)
An Alternate Proof of Near-Optimal Light Spanners
Fault-Tolerant ST-Diameter Oracles (Manish)
Please read the IIT Gandhinagar Honor Code.
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
Probability and Computing by Michael Mitzenmacher and Eli Upfal
Approximation algorithms by Vijay Vazirani
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.