COL351 – Analysis & Design of Algorithms

Weekly Lecture Plan

Week 1

Graph Traversals (Undirected)

DFS in undirected graphs
Connected components
2-edge-connected and biconnected graphs
BFS and bipartiteness

Week 2

Directed Graphs

DFS in directed graphs
Topological sort
Strong connectivity and SCCs

Problem Sheet 1

Week 3

Greedy Algorithms I

Fractional knapsack
Deadline scheduling
Activity selection

Problem Sheet 2

Week 4

Greedy Algorithms II

Minimum spanning trees (Kruskal, Prim)
Union-find data structure

Problem Sheet 3

Week 5

Divide and Conquer I

Merge sort, Quicksort, Counting inversions
Recursion trees and solving recurrences
Finding median
Randomized and deterministic selection

Problem Sheet 4

Week 6

Divide and Conquer II

Closest pair, Maximal points
FFT, Polynomial evaluation

Problem Sheet 5
Problem Sheet 6

Week 7

Dynamic Programming I

Integer knapsack
Longest increasing subsequence
Maximum independent set on a tree

Problem Sheet 7

Week 8

Dynamic Programming II

Matrix chain multiplication
Longest common subsequence

Problem Sheet 7

Week 9

Shortest Paths I

Shortest and longest path in DAGs
Dijkstra’s algorithm
Shortest path tree

Problem Sheet 8

Week 10

Shortest Paths II

Bellman-Ford for negative weights
Floyd-Warshall for all pairs

Problem Sheet 9

Week 11

Network Flows I

Flow concepts: capacity, conservation, residual graph
Ford-Fulkerson algorithm
Maxflow-min cut theorem

Problem Sheet 11

Week 12

Network Flows II

Flows with bounds
Circulation
Applications: assignment, matching, projects

Problem Sheet 12

Week 13

Intractability

Polynomial time, decision vs optimization
Reductions: SAT, 3-SAT, CLIQUE, VC, IS
Eulerian and Hamiltonian graphs

Problem Sheet 13

Text and Reference Material

Algorithms Design by Jon Kleinberg and Eva Tardos
Slides for this text book can be found here
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press and McGraw-Hill.
Algorithms by Dasgupta, Papadimitriou and Vazirani
Pat Morin's course on Advanced Data Structures
Lecture Notes on Algorithms by Jeff Erickson, UIUC
Lecture Notes on Algorithms by Sariel Har Peled, UIUC

Evaluation & Attendance Policy

Midterm (25), Major (35), Quizzes (2x15), Attendance (5L, 5T)
If you miss the midterm or one of the quizzes due to illness (medical certificate needed) and if you have at least 75% attndance in the lectures and tutorials (combined), then I will scale the marks you receive in the other evaluations to award you marks in the missed midterm/quiz. There is no reexam. Marks for only one exam will be awarded in this manner.

TAs and Contact

Instructor: Naveen Garg, Bharti 515, naveen@cse.iitd.ac.in

Teaching Assistants:

Sukriti Gupta csz258469@iitd.ac.in
Serene Rasheed csz258234@iitd.ac.in
Rohan Chaturvedi mt1221262@iitd.ac.in
Rishik Saha cs1221932@iitd.ac.in

Analysis & Design of Algorithms (COL351)