| Course Outline | General Information | Study Material | Lectures (classwise) | Useful Links |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study Graph Algorithms from a combinatorial optimization standpoint. We will first focus on polynomially solvable problems in graphs mainly focussing on shortest paths, network flow, matching, etc. . We would then move towards NP-hard problems and approximation algorithms for them.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Structures courses.
| Class Timings: | Wednesday 09:30-11:15, Friday 09:30-11:15 Room No. 719, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(1) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (2) Algorithmic Graph Theory and Perfect Graphs M. C. Golumbic Academic Press (3) M. R. Garey and D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman (4) Approximation Algorithms V. V. Vazirani Springer (5) Approximation Algorithms for NP-Hard problems D. S. Hochbaum (edited) Thomson (6) An Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Prentice Hall India. |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (06-08-08) |
Shortest path: Dijkstra's algorithm | - | (1), (6) |
| Lecture 2 (08-08-08) |
Shortest path: Dijkstra's algorithm Matroids: Theoretical Foundation for Greedy paradigm |
- | (1), (6) |
| Lecture 3 (13-08-08) |
Matroids: Theoretical Foundation for Greedy paradigm | - | (6) |
| Lecture 4 (27-08-08) |
Network Flow: Max-Flow Min-Cut Theorem | - | (1) |
| Lecture 5 (3-09-08) |
Network Flow: Preflow Push and relabel | - | (1) |
| Lecture 6 (5-09-08) |
Network Flow: Preflow Push and relabel | - | (1) |
| Lecture 7 (8-09-08) |
Network Flow and bipartite matching | - | (1) |
| Mid Semester | Model Solution | - | - |
| Lecture 8 (17-10-08) |
Introduction to NP-Completeness and Approximation Algorithms | - | (3, 4) |
| Lecture 9 (24-10-08) |
Bin Packing | - | (4, 5) |
| Lecture 10 (27-10-08) |
Inapproximability of TSP, Euclidean TSP |
- | (4) |
| Lecture 11 (29-10-08) |
Euclidean TSP, Introduction to (F)PTAS |
- | (4) |
| End Semester | Model Solution | - | - |