| Course Outline | General Information | Study Material | Lectures (classwise) | Announcements (updated on April 7, 2017) some slides added/a> |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study design paradigms for algorithms and their analysis.
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 Introduction to Programming and Data Structures and Discrete Mathematics courses and have some knowledge of elementary discrete probability.
| Class Timings: | Tuesday 11:15-13:00, Thursday 11:15-13:00, Friday 11:15-13:00 Room No. 705-706, S. N. Bose Bhavan (Library Building) |
| Exams -- the necessary evil: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (Indian edition) (B2) Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein Prentice Hall India. (B3) The Design and Analysis of Computer Algorithms A. V. Aho, J. E. Hopcroft and J. D. Ullman Pearson (B4) Algorithms S. Dasgupta, C. Papadimitriou and U. Vazirani Tata McGraw-Hill (B5) Probability and Computing: Randomized Algorithms and Probabilistic Analysis Michael Mitzenmacher and Eli Upfal Cambridge University Press (B6) A First Course in Probability Sheldon Ross Pearson (B7) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag (B8) Approximation Algorithms Vijay V. Vazirani Springer (B9) The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Cambridge |
| Web Resources |
(W1)
Lecture Notes by Prof. David Mount (W2) Lecture Notes by Prof. Sandeep Sen (W3) Lecture Notes by Prof. David Mount on Computational Geometry |
| LECTURE DATES | TOPICS and REFERENCES | NOTES (pdf) |
| Lecture 1 (03-01-17) |
Introduction, efficiency of an algorithm -- [(B1), (B2), (B4)]
RAM Model of computation, etc. -- [(B1), (B4), (Section 1.3 and 1.4 of W2)] |
- |
| Lecture 2 (05-01-17) |
Convex Hull: lower bound, Graham's scan algorithm,
proof of correctness, etc. -- [(Chapter 1 of B7), (W3)] |
- |
| Lecture 3 (06-01-17) |
Jarvis March for convex hull -- [(W3)] Asymptotic notation: big-oh, big-omega, theta, small-oh Introduction to sorting: merge sort, insertion sort, quick sort, etc.; -- (B1), (B2), (B3) |
- |
| Lecture 4 (12-01-17) |
Recurrences: divide and conquer, linear homogeneous and inhomogeneous recurrence; Problems around recurrences -- (B1), (B2), (B3), (W2) |
- |
| Lecture 5 (13-01-17) |
Tutorial 1 | Tutorial Sheet 1 |
| Lecture 6 (17-01-17) |
Lower bound on the worst case of sorting; Heapsort; Quicksort (worst case) -- (B3), (B2) |
- |
| Lecture 7 (20-01-17) |
Building heap in linear time -- (B2), (B3) probabilistic analysis (average case) of deterministic quick sort -- [(B3), (B2)] randomized quick sort -- [(B5), (B6), (B2)] |
- |
| Lecture 8 (24-01-17) |
Lower bound for average case in sorting -- [(B3)] Counting sort, Radix Sort, Bucket sort -- [(B2)] |
- |
| Lecture 9 (27-01-17) |
Selection -- [(B3)] Tutorial 2 |
Tutorial Sheet 2 |
| Lecture 10 (31-01-17) |
Algorithmic paradigms: Greedy and Divide and conquer Greedy: Interval scheduling -- [(B1)] Divide and conquer: Closest pair -- [(B1)] |
- |
| Lecture 11 (02-02-17) |
Algorithmic paradigm -- Dynamic Programming: Longest increasing subsequence -- [(B4)] Longest common subsequence -- [(B2)] Matrix chain multiplication -- [(B4)] |
- |
| Lecture 12 (03-02-17) |
Introduction to Linear Program and Integer Linear Program (ILP) -- [(B4), (B2)] Writing Knapsack as an ILP; Algorithmic paradigm -- Dynamic Programming: Knapsack [(B4), (B8)] |
- |
| Lecture 13 (07-02-17) |
Introduction to graph algorithms:
Graph representation: adjacency matrix and adjacency list Graph exploration: Breadth First Search (BFS) -- [(B2)] Depth First Search (DFS) -- [(B4), (B2)] |
- |
| Lecture 14 (09-02-17) |
Depth First Search (DFS): DAG, topological sort, strongly connected component -- [(B4), (B2)] |
- |
| Lecture 15 (10-02-17) |
Shortest Path in Graph: Dijkstra's algorithm -- [(B1), (B4), (B2)] | - |
| Lecture 16 (14-02-17) |
Tutorial-3 | Tutorial Sheet 3 |
| Lecture 17 (16-02-17) |
Another application of DFS: Finding cut vertices in an undirected graph -- [(W3)] Minimum Spanning tree: characterizations and Prim's algorithm -- [(B1)] |
- |
| Class Test 1 (17-02-17) |
Sketch of the solutions | - |
| Mid Semestral Exam (21-02-17) |
Sketch of the solutions | - |
| Lecture 18 (28-02-17) |
Use of d-ary heap in Dijkstra's algorithm [(B4)] Bellman-Ford algorithm for shortest path algorithm [(B1, B4)] Floyd Warshall algorithm for All Pair Shortest Path [(B4)] |
- |
| Lecture 19 (02-03-17) |
Huffman encoding: another greedy algorithm [(B1), (B4)] | - |
| Lecture 20 (03-03-17) |
Network Flow -- Ford Fulkerson [(B1), (B4)] | - |
| Lecture 21 (07-03-17) |
Hashing -- [(B1), (B4)] | Online notes (by Sariel Har-Peled) |
| Lecture 22 (09-03-17) |
Tutorial-4 | Tutorial Sheet 4 |
| Lecture 23 (14-03-17) |
Network Flow: max flow -- min cut [(B1), (B4)] | - |
| Lecture 24 (16-03-17) |
Bipartite matching (use of network flow) -- [(B1)] Kruskal's algorithm for minimum spanning tree and use of Union Find data structure -- [(B1), (B3)] |
- |
| Lecture 25 (17-03-17) |
Union Find (path compression) [(B3)] | - |
| Lecture 26 (21-03-17) |
Randomized algorithm for min-cut in an undirected graph [(B1)] | - |
| Lecture 27 (23-03-17) |
Skip List [(W2), Lecture notes] | - |
| Lecture 28 (28-03-17) |
String Matching: Rough sketch of Rabin Karp fingerprinting [(B2), (W2)] Knuth Morris Pratt algorithm [(B2), (W2), Lecture notes] |
- |
| Lecture 29 (30-03-17) |
Computational Geometry: Finding the area of a simple polygon [(B7), (W3)] Line Segment Intersection [(B7), (W3)] | - |
| Lecture 30 (31-03-17) |
Polynomial reducibility and its consequences -- [(B1), (B4), (B2)] | - |
| Lecture 31 (05-04-17) |
NP-Completeness -- [(B1), (B4), (B2)] | - |
| Lecture 32 (06-04-17) |
NP-Completeness [(B1), (B4), (B2)] | Slides |
| Lecture 33 (06-04-17) |
Approximation Algorithm: Vertex cover, Bin packing -- [(B8), (B9)] Hardness of approximation for TSP [(B9)] |
Slides (look for introduction to approximation algorithm at the end) |
| Lecture 34 (07-04-17) |
Approximation Algorithm: Metric TSP -- [(B9)] FPTAS for Knapsack [(B8)] |
- |