- Study material: Keep looking regularly for any updates
| Text Book | Introduction to Algorithms: A Creative Approach Udi Manber Addison Wesley |
| Other readings | Algorithms: Design Techniques and Analysis M. H. Alsuwaiyel World Scientific Computational Geometry - Algorithms and Applications M. De Berg, M. Kreveld, M. Overmars, O. Schwarzkopf Professor David Mount's lecture notes Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Prentice Hall of India. The Design and Analysis of Computer Algorithms A. V. Aho, J. E. Hopcroft and J. D. Ullman Addison Wesley Computer Algorithms: Introduction to Design and Analysis S. Baase Addison Wesley Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan Cambridge University Press |
| LECTURE DATES | TOPICS | SCRIBE NOTES (pdf) |
| Lecture 1 (24-7-06) | Introductory Lecture. | - |
| Lecture 2 (25-7-06) | Induction: regions in the plane, colouring, Euler's formula Assymptotic notations | |
| Lecture 3 (26-7-06) | Assymptotic notations, Why fixing the size of the input is important? Loop invariance, Pigeonhole principle | - |
| Lecture 4 (1-8-06) | Linear Homogenous and non-homogenous recurrences | |
| Lecture 5 (2-8-06) | Divide and conquer recurrences and recurrence with full history | |
| Lecture 6 (7-8-06) | A brief discussion on paradigms of algorithm design, Some examples: majority finding (induction), binary search (recursion), minimum and maximum finding (recursion), Fibonacci number (dynamic programming) average case analysis of quick sort. | |
| Lecture 7 (8-8-06) | Worst case and average case lower bounds for comparison based sorting. | |
| Lecture 8 (9-8-06) | Non-comparison based linear time sorting: counting sort, radix sort and bucket sort | |
| Lecture 9 (10-8-06) | Selection in worst case linear time. | |
| Lecture 10 (16-8-06) | Integer exponentiation, Multiplication of large integers, and Strassen's Matrix multiplication | |
| Lecture 11 (21-8-06) | Union-Find by rank heuristic | |
| Lecture 12 (22-8-06) | Union-Find by path compression | |
| Lecture 13 (23-8-06) | Union-Find by path compression (contd.) | |
| Lecture 14 (28-8-06) | Tutorial-I | |
| Lecture 15 (29-8-06) | Dynamic Programming | |
| Lecture 16 (30-8-06) | Dynamic Programming | |
| Class Test I (30-8-06) | Class Test I | - |
| Lecture 17 (4-9-06) | Dynamic Programming | - |
| Lecture 18 (5-9-06) | Convex hull | |
| Lecture 19 (6-9-06) | Shortest pair among a point set | |
| Lecture 20 (11-9-06) | Diameter of a point set, Voronoi diagram | |
| Lecture 21 (12-9-06) | Voronoi diagram | |
| Lecture 22 (13-9-06) | Some problems on Voronoi diagram | - |
| Mid Sem (19-09-06) | Mid semester exam | - |
| Lecture 23 (27-9-06) | Dijkstra's shortest path | |
| Lecture 24 (9-10-06) | Dijkstra's shortest path, Huffman encoding | |
| Lecture 25 (10-10-06) | Bellman-Ford, Kruskal's Minimum Spanning tree | |
| Lecture 26 (11-10-06) | Matroids | |
| Lecture 27 (17-10-06) | Matroids | - |
| Lecture 28 (18-10-06) | Matroids | - |
| Lecture 29 (24-10-06) | Network Flows | |
| Lecture 30 (26-10-06) | Network Flows | |
| Lecture 31 (30-10-06) | Network Flows | |
| Lecture 32 (31-10-06) | Network Flows | |
| Lecture 33 (01-11-06) | Bipartite matching | |
| Lecture 34 (02-11-06) | KMP | |
| Lecture 35 (06-11-06) | KMP | |
| Lecture 36 (06-11-06) | NP Completeness | |
| Lecture 37 (07-11-06) | NP Completeness | |
| Class Test II (07-11-06) | Class Test II | - |
| Lecture 38 (08-11-06) | NP Completeness | |
| Lecture 39 (13-11-06) | Approximation Algorithm | |
| Lecture 40 (13-11-06) | Approximation Algorithm | |
| Lecture 41 (14-11-06) | Approximation Algorithm | - |
| Lecture 42 (15-11-06) | Approximation Algorithm | - |
| Class Test III (16-11-06) | Class Test III | - |
| Class Test I, Autumn 2005 | |
| Class Test II, Autumn 2005 | |
| Class Test III, Autumn 2005 | |
| Mid sem, Autumn 2005 | |
| End sem, Autumn 2005 | |
| Class Test I, Autumn 2006 | |
| Class Test II, Autumn 2006 | |
| Class Test III, Autumn 2006 | |
| Mid sem, Autumn 2006 | |
| End sem, Autumn 2006 |
No comments:
Post a Comment