Analysis & Design of Algorithms (COL351)

Instructor: Naveen Garg, Bharti 515

Lectures: TWF10-11, LH114 • Tutorials: MTThF 1–2 pm, LH517

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

Week 8

Dynamic Programming II

  • Matrix chain multiplication
  • Longest common subsequence

Week 9

Shortest Paths I

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

Week 10

Shortest Paths II

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

Week 11

Network Flows I

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

Week 12

Network Flows II

  • Flows with bounds
  • Circulation
  • Applications: assignment, matching, projects

Week 13

Intractability

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

Text and Reference Material

Evaluation & Attendance Policy

TAs and Contact

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

Teaching Assistants:

© IIT Delhi – COL351 (Analysis & Design of Algorithms)