# COL 702 : Advanced Data-structures and Algorithms

## Course Coordinator

Amit Kumar

Office : Room # 417, Bharti Building

Email : amitk@cse.iitd.ac.in

Phone : (ext) 1286.

## Announcements

Teaching assistants: Mayank Jain, Shailja Pandey

## Class Timings

Monday, Thursday : 8am-9:30am

## Assignments

## Lecture Topics

- Lecture 1: Introduction to the course, Time and space complexity

- Lecture 2: Graphs, data-structures for graphs, basic terminologies

- Lecture 3: Trees, depth first search

- Lecture 4: Properties of DFS, strong connectivity, topological sort

- Lecture 5: strongly connected components using DFS

- Lecture 6: 2-edge connectivity, Breadth First Search (BFS)

- Lecture 7: Properties of BFS, Bellman-Ford Algorithm

- Lecture 8: Bellman-Ford algorithm, Dijkstra's Algorithm

- Lecture 9: Greedy Algorithms, Minimum Spanning Trees

- Lecture 10: More example of Greedy Algorithms

- Lecture 11: SRPT Scheduling Algorithm, Idea of Amortized Analysis

- Lecture 12: Splay Trees

- Lecture 13: Divide and Conquer: Merge sort, randomized quick sort

- Lecture 14: Deterministic median finding, closest pair of points

- Lecture 15: Dynamic Programming: Basic examples

- Lecture 16: Dynamic Programming: idea of median row in table to save space

- Lecture 17: Maximum flow problem: Augmenting Path Algorithm

- Lecture 18: Maximum flow: Capacity Scaling Algorithm, flow decomposition

- Lecture 19: Applications of max-flow: disjoint path, matching, Hall's theorem

- Lecture 20: Applications of max-flow: project selection, circulation problem, flows with lower bounds

- Lecture 21: Min-cost flow and cycle cancelling algorithm

## Books

There is no required textbook for this course. But most of the topics
covered can be found in the following book.

- Algorithms Design: Jon Kleinberg and Eva Tardos
- Design and Analysis of Algorithms: Sandeep Sen and Amit Kumar

## Grading (tentative)

20% : Homework

20% : Each minor exam

40% : Major exam