| Course Outline | General Information | Study Material | Lectures (classwise) | Announcements (new assignment added) |
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 14:15-16:00, Thursday 09:30-11:10, Friday 14:15-16:00 Room No. 520, 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 (B10) Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan Cambridge University Press (B11) Understanding and Using Linear Programming Jiří Matoušek and Bernd Gärtner Springer |
| Web Resources |
(W1)
Lecture Notes by Prof. David Mount (on algorithms) (W2) Lecture Notes by Prof. Sandeep Sen (updated link) (W3) Lecture Notes by Prof. David Mount on Computational Geometry (W4) Approximation Algorithm book |
| LECTURE DATES | TOPICS and REFERENCES | NOTES (pdf) |
| Lecture 1 (01-01-19) |
Introduction, efficiency of an algorithm -- [(B1), (B2), (B3), (B4)]
RAM Model of computation, uniform cost model, logarithmic cost model, etc. -- [(B1),(B3),(B4), (Sections 1.3, 1.4 and 1.5 of W2)] |
- |
| Lecture 2 (03-01-19) |
Worst case lower bound on comparison based sorting using decision tree -- [(B2), (B3)]
recurrence for divide-and-conquer algorithms for sorting -- [(B2)] average case analysis of quicksort --- [(B2), (B3)] |
- |
| Lecture 3 (08-01-19) |
Average case lower bound on comparison based sorting using decision tree -- [(B3)]
Randomized quicksort -- [(B5)] Heap -- [(B3)] |
- |
| Lecture 4 (11-01-19) |
Sorting with extra information: counting sort -- [(B2)], radix sort -- [(B2), (B3)], bucket sort -- [(B2)] | - |
| Lecture 5 (15-01-19) |
Selection: an application of waiting for success bound -- [(B1)] Randomized selection -- [(B3), (W2)] Deterministic selection -- [(B3), (W2)] |
- |
| Lecture 6 (17-01-19) |
Skip List -- [(B10), (W2)] 1d Range searching [(B7), (W3), (W2)] |
- |
| Lecture 7 (18-01-19) |
Range Tree, Kd-tree -- [(B7), (W3), (W2)] | - |
| Lecture 8 (22-01-19) |
Convex Hull: Jarvis March and Graham's scan algorithm -- [(B7), (W2), (W3)] | - |
| Lecture 9 (24-01-19) |
Convex Hull: Divide and conquer algorithm, Chan's output sensitive algorithm -- [(B7), (W2), (W3)] | - |
| Lecture 10 (25-01-19) |
Closest Pair, Line Segment Intersection -- [(B7), (W3)] Tutorial - I |
- |
| Lecture 11 (29-01-19) |
Greedy Paradigm: Interval scheduling, Huffman encoding -- [(B1)] | - |
| Lecture 12 (31-01-19) |
Greedy Paradigm: Huffman encoding (contd.) -- [(B1)], Scheduling all intervals on minimum number of machines -- [(B1)] |
- |
| Lecture 13 (01-02-19) |
Class Test 1, Dynamic Programming: Longest common subsequence -- [(W1)] Knapsack -- [(W3)] |
- |
| Lecture 14 (05-02-19) |
Dynamic Programming: Knapsack -- [(B8)], Weighted Interval Scheduling -- [(B1)] Matrix Chain Multiplication -- [(W1)] |
- |
| Lecture 15 (07-02-19) |
Graph Storage: Adjacency list, adjacency matrix Breadth First Search -- [(W1), (B4)] |
- |
| Lecture 16 (08-02-19) |
Depth First Search, DAG -- [(W1),(B4)] | - |
| Lecture 17 (12-02-19) |
Depth First Search, Topological Sort, Strongly connected component -- [(W1),(B4)] | - |
| Lecture 18 (14-02-19) |
Shortest Path: Dijkstra's algorithm, Bellman-Ford algorithm -- [(B1),(B4),(W1),(W2)] | - |
| Class Test II (15-02-19) |
Class Test II model solution | - |
| Mid Semestral exams (22-02-19) |
Mid Sem model solution (only for Group-B questions) | - |
| Lecture 19 (26-02-19) |
Shortest Path: Bellman-Ford algorithm -- [(B1),(B4),(W1),(W2)] All pair shortest path: Floyd Warshal algorithm [(B4),(B3)] Minimum Spanning Tree: Kruskal and Prim's algorithm [(B1), (B4)] |
- |
| Lecture 20 (28-02-19) |
Minimum Spanning Tree, Union Find: Analysis of union by rank -- [(B1), (B4), (B2), (B3), (W2)] | - |
| Lecture 21 (01-03-19) |
Tutorial II | - |
| Lecture 22 (05-03-19) |
Union Find: Analysis of Path Compression -- [(B4),(B3),(B2),(W2)] Network Flow and LP, initial ideas of polynomial reducibility -- [(B4)] |
- |
| Lecture 23 (06-03-19) |
Network Flow: Ford and Fulkerson algorithm, Max Flow Min Cut -- [(B1),(B4),(W1),(W2)] | - |
| Lecture 24 (08-03-19) |
Network Flow, Bipartite matching -- [(B1),(B4),(W1),(W2)] | - |
| Lecture 25 (12-03-19) |
Tutorial -- III | - |
| Lecture 26 (13-03-19) |
Linear Programming -- [(B11), B4)] | - |
| Lecture 27 (14-03-19) |
Linear Programming -- [(B11),(B4)] | - |
| Lecture 28 (19-03-19) |
Linear Programming -- [(B11),(B4)] | - |
| Lecture 29 (20-03-19) |
String Matching: KMP -- [(W2)] | Hand out provided |
| Lecture 30 (26-03-19) |
Fast Fourier Transform -- [(B1),(B4)] | - |
| Lecture 31 (28-03-19) |
Fast Fourier Transform -- [(B1),(B4)] | - |
| Lecture 32 (29-03-19) |
Polynomial reduction: Definition, implications and transitivity Polynomial reduction and a few problems -- SAT, 3SAT, Clique, ILP |
Slides for Polynomial reduction and NP Completeness |
| Lecture 33 (02-04-19) |
Polynomial reduction: Vertex Cover, Independent Set, Hamiltonian Cycle, TSP; Classes P and NP, NP-Complete --- [(B1), (B4)] |
-- |
| Lecture 34 (04-04-19) |
NP-Complete, Co-NP and the relations among P, NP, co-NP [(B1),(B4)] | -- |
| Lecture 35 (05-04-19) |
Approximation Algorithms: Constant factor approximation --- Bin Packing, Cardinality Vertex Cover, Weighted Vertex Cover (B4,B11,W4) |
Slides for Approximation Algorithm |
| Lecture 36 (09-04-19) |
Inapproximability of TSP -- [(W4),(B8),(B4)]; 2-factor for Euclidean TSP -- [(W8),(B8),(B4)]; 2-factor for k-center [(B4),(W8),(B8)], FPTAS for Knapsack [(B8),(W4)] |
-- |
| Lecture 37 (11-04-19) |
Relation between Strongly NP-hard, FPTAS and Pseudo-polynomial time algorithm -- [(B8)], Introduction to Parameterization -- Branching and FPT algorithm for Vertex Cover -- [(B1)] Randomized incremental 2D LP -- [(W3), (B7)] |
Handout given in class |
| Lecture 38 (11-04-19) |
Streaming algorithms | Handout given in class |
| End Semestral exams (18-04-19) |
End Sem model solution (only some Group-A answers are there) | - |