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 [JE]- Jeff Erickson [link]
Introduction to Algorithms [CLRS] - 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]).
Lecture-5: Graphs: BFS/DFS correctness, generic strategy for traversal (Reference: Chapter 3, Section 3.2 [KT]).
Lecture-6: Graphs: BFS/DFS implementation, testing bipartiteness (Reference: Chapter 3, Section 3.3, 3.4 [KT]).
Lecture-7: Graphs: Connectivity in directed graphs: Strongly connected components (Reference: Chapter 3, Section 3.5 [KT]); Reading Exercise: Analysis of Kosaraju's algorithm for finding SCCs in linear time (Reference: Chapter 6, Section 6.5,6.6 [JE])
Lecture-8: Graphs: Directed acyclic graphs and topological ordering (Reference: Chapter 3, Section 3.6 [KT]); Introduction to greedy algorithms.
Lecture-9: Greedy algorithms: Interval scheduling problem and its variants (Reference: Chapter 4, Section 4.1 [KT]).
Lecture-10: Greedy algorithms: Interval partitioning problem (Reference: Chapter 4, Section 4.1 [KT]).
Lecture-11: Greedy algorithms: Scheduling to minimize lateness (Reference: Chapter 4, Section 4.2 [KT]).
Lecture-12: Greedy algorithms: Optimal Caching (Reference: Chapter 4, Section 4.3 [KT]).
Lecture-13: Greedy algorithms: Shortest Paths in a Graph- Dijkstra's algorithm and analysis (Reference: Chapter 4, Section 4.4 [KT]).