| 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 | - |
