COL 702 : Advanced Data-structures and Algorithms

Course Coordinator

Announcements

Class Timings

Assignments

• Homework 1 (Due on 19th August)
• Homework 2 (Due on 4th September)
• Homework 3 (Due on 19th September)
• Homework 4 (Due on 17th October)
• Homework 5 (Due on 4th November)

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

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

Grading (tentative)