Course Instructor: Dalu Jacob, Office: 527 B, dalujacob@math.iitd.ac.in
Time and Venue: Tue, Thu, Fri 11:00-12:00, LH 318
Teaching Assistants:
Soumyasree Rana, maz218122@maths.iitd.ac.in
Sahiba, maz238701@maths.iitd.ac.in
Tatsam Ranjan Sharma, mt6221969@maths.iitd.ac.in
Tutorial Slots:
Syllabus
Asymptotic notation; DFS, BFS, and some applications; Greedy algorithms: interval scheduling, optimal caching, minimum spanning trees (Prim’s and Kruskal’s ), shortest path, etc.; Divide and Conquer: sorting, matrix multiplication, etc.; Dynamic Programming: scheduling, subset sum, etc.; Network Flow algorithms and applications; NP-completeness and reductions; Introduction to Approximation algorithms and Randomized algorithms.
Evaluation Plan
3 Quizzes (10 marks each): 30 marks
Minor: 30 marks
Major: 35 marks
Attendance: 5 marks for at least 80% (2 marks for [75,8))
To audit pass the course, you need to have at least 35 marks, at least 25 of which should come from minor and major.
Remark: The re-minor and re-quiz examinations will be conducted together towards the end of the semester. Therefore, you may miss at most one of the quizzes or the minor exam.
Office hours: By email appointment
References
Primary reference [KT]: Algorithm Design - John Kleinberg, Eva Tardos, published by Pearson. A low-priced edition is available in India.
Lecture slides on the chapters of the book are available at [link]
Additional references:
Algorithms - Jeff Erickson [link]
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein [link]
Algorithms - Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou [link]
Topics covered
Lecture-1: Introductory session (no specific reference).
Lecture-2: Stable Matching: Gale-Shapley algorithm analysis (Reference: Chapter 1, Section 1.1, [KT]), Asymptotic upper and lower bounds of algorithms (Reference: Chapter 2, Sections 2.1, 2.2 [KT]).
Lecture-3: Properties of Asymptotic bounds (Reference: Chapter 2, Section 2.2 [KT]), Some Common running times with examples (Reference: Chapter 2, Section 2.4 [KT]).
Lecture-4: Graphs: Basic definitions and applications, Representation of graphs (Reference: Chapter 3, Section 3.1 [KT]).