Course Instructor: Dalu Jacob, Office: MGGP- GPF-2, dalujacob@math.iitd.ac.in
Time and Venue: Tue, Thu, Fri 11:00-12:00, LH 316
Teaching Assistants:
Soumyasree Rana, maz218122@maths.iitd.ac.in
Rumki Ghosh, maz218120@maths.iitd.ac.in
Vishvesh Patel, mt6200896@maths.iitd.ac.in
Rakshitha, mt1210904@maths.iitd.ac.in
Tutorial Slots: Wed 14:00-15:00, Thu 13:00-14:00
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
2 Quizzes (best of three)+ 1 Assignment: 30 marks (10 marks each)
Minor: 30 marks
Major: 40 marks
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: No re-quizzes will be conducted
Attendance Policy: Attendance in the lecture class is to be maintained as per the Institute rules.
References
Primary reference: Algorithm Design - John Kleinberg, Eva Tardos
Lecture slides on the chapters of the book are available at [link]
Additional references:
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein [link]
Algorithms - Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou [link]
Algorithms - Jeff Erickson [link]
Topics covered
Week 1: Orders of magnitude, Asymptotic upper and lower bounds of algorithms, Properties of asymptotic growth rates, Some common running times with examples (Reference: Chapter 2, Algorithm Design), Introduction to graphs (Reference: Chapter 3, Algorithm Design).
Week 2: Introduction to graphs, Representation of graphs, Graph connectivity, BFS and DFS traversals, Implementation of BFS and DFS, Applications of BFS and DFS: finding the set of all connected components, checking bipartiteness, connectivity in directed graphs, strongly connected components, Directed acyclic graphs and topological ordering (Reference: Chapter 3, Algorithm Design).
Week 3: Greedy Algorithms: Interval scheduling problem, Interval partitioning problem, Scheduling to minimize lateness, Optimal caching (Reference: Chapter 4, Algorithm Design).
Week 4: Shortest Path problem (Dijkstra's algorithm) (Reference: Chapter 4, Algorithm Design).
Week 5: The Minimum Spanning tree problem (Prim's and Kruskal's algorithm), Implementation of Prim's and Kruskal's -- Union find data structure (Reference: Chapter 4, Algorithm Design), Divide and Conquer: The merge sort algorithm and further recurrence relations (Reference: Chapter 5, Algorithm Design).
Week 6: Counting inversions, Finding the closest pair of points, Integer multiplication (Reference: Chapter 5, Algorithm Design), Matrix multiplication (Reference: Chapter 4, CLRS), Convolutions and its applications (Reference: Chapter 5, Algorithm Design).
Week 7: Convolutions and Fast Fourier Transform: Computation (Reference: Chapter 5, Algorithm Design), Dynamic Programming: Weighted interval scheduling (Reference: Chapter 6, Algorithm Design).
Week 8: Segmented least squares , Subset sums, Knapsacks and its variants, RNA Secondary structure: Dynamic Programming over intervals (Reference: Chapter 6, Algorithm Design).
Week 9: Sequence alignment, Space efficient alignment, Shortest paths in graphs: Bellman-Ford algorithm (Reference: Chapter-6, Algorithm Design), Floyd-Warshall algorithm.
Week 10: Network Flow: Introduction, Ford-Fulkerson algorithm, Maximum flows and Minimum cuts, Max Flow-Min Cut theorem, Choosing good augmenting paths, A faster flow algorithm (Reference: Chapter 7, Algorithm design).
Week 11: The Preflow-Push Max-flow algorithm, Network Flow applications; Bipartite matching (Reference: Chapter 7, Algorithm design).
Week 12: Network Flow applications; Disjoint paths in directed and undirected graphs, circulation with demands and lower bounds, survey design, etc. (Reference: Chapter 7, Algorithm design).
Week 13: NP and Computational intractability; Some well-known problems, Efficient certifiers, P Vs NP, Polynomial-time reductions, NP-completeness (Reference: Chapter 8, Algorithm design).
Week 14: NP and Computational intractability; More NP-complete problems and their reductions; 3SAT, Independent set, Vertex cover, Set cover, Traveling Salesman Problem, Hamiltonian cycle problem (Reference: Chapter 8, Algorithm design).
Week 15: Feedback vertex set Problem, Introduction to approximation algorithms, vertex cover approximation algorithm, Linear Programming in approximation algorithms; ILP formulation of problems, weighted vertex cover.