Advanced Data Structures and Algorithms

Course code	COL702
Instructor	Ashish Chiplunkar (ashishc@...)
Teaching Assistants	Kartik Jain, Saumya Gupta
Classes	Monday and Thursday 08:00 - 09:30 (Slot A), Wednesday 13:00 - 14:00
Office hour	TBD

Prerequisites

Induction / recursion, asymptotic notation, recurrence relations
Data structures: linked lists, stacks, queues, binary trees, heaps
Algorithms: binary search, sorting
Graph concepts: undirected and directed graphs, trees, forests, cycles, directed acyclic graphs, connectivity and strong connectivity, adjacency matrix and adjacency list representations
Graph algorithms: breadth-first and depth-first traversals and their applications, Dijkstra's algorithm for single source shortest path, Kruskal's algorithm for minimum weight spanning tree

Content (tentative)

Algorithm design techniques: divide and conquer, dynamic programming, greedy
Data Structures and amortized analysis: AVL trees, binomial heaps, Fibonacci heaps, union-find
Augmentation: maxflow-mincut, bipartite matchings
NP-completeness: reduction, polynomial-time verification, Cook-Levin theorem
Randomized Algorithms

Textbooks

"Algorithm Design" by Jon Kleinberg and Éva Tardos
"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Known Overlapping Courses

COL351, ELL781, MTL342. Students who have done or are currently doing any of these courses might be disallowed from taking COL702 for a grade (but will be allowed to attend). If you think you have done or are currently doing any other course with significantly overlapping content, please send an email to the instructor.

Useful Platforms

Moodle for announcements and discussions
Impartus for live and recorded lectures
Gradescope for exams

Grading (tentative)

Class participation	10%
Homeworks	25%
Quizzes	30%
Major exam	35%