COL 351 : Analysis and Design of Algorithms
Required Textbook
    Title : Algorithm Design.
    Authors : Jon Kleinberg and Eva Tardos
Supplementary Text: Algorithms, by Dasgupta, Papadimitriou, and Vazirani
   
Other references
  1. Notes on dynamic programming (by Jeff Erickson)
  2. Notes on bipartite matching (by Michel Goemans)
Lecture Topics
- Lecture 1: Introduction, Big O() notation
- Lecture 2: Greedy Algorithms. Interval Selection Problem.
- Lecture 3: Exchange argument. Minimum Average Completion Time.
- Lecture 4: Deadline Scheduling. Review of Graphs.
- Lecture 5: Kruskal's algorithm for minimum spanning tree
- Lecture 6: Union Find Data-structure, Huffman codes
- Lecture 7: Huffman coding algorithm
- Lecture 8: Stable matching
- Lecture 9: Dijkstra's algorithm for shortest path
- Lecture 10: Dijkstra's algorithm for shortest path, Divide and Conquer Algorithms
- Lecture 11: Randomized Quicksort
- Lecture 12: Randomized and Deterministic Selection
- Lecture 13: Closest Pair of Points
- Lecture 14: Integer Multiplication
- Lecture 15: Polynomial multiplication, FFT
- Lecture 16: applications of FFT, FFT algorithm
- Lecture 17: Introduction to dynamic programming, coin changing problem
- Lecture 18: Weighted Interval selection problem, Edit Distance
- Lecture 19: Multiplying several matrices
- Lecture 20: All pairs shortest path
- Lecture 21: All pairs shortest paths. Introduction to bipartite matching
- Lecture 22: Augmenting path algorithm, Hall's theorem.
- Lecture 23: Applications of Hall's theorem.
- Lecture 24: Introduction to Max Flow
- Lecture 25: Ford-Fulkerson Algorithm for Max Flow
- Lecture 26: Applications of Max Flow, Flow Decomposition
Lecture Timings
  Monday, Wednesday 11:00-11:50, Thursday 12:00-12:50
  Venue : LH 316
Tutorials
  Monday 3-4pm, Wed 1-2pm, Thursday 4-5pm. Venue : LH 519.
 
    Tutorial 1
    Tutorial 2
    Tutorial 3
    Tutorial 4
    Tutorial 5
    Tutorials 6-7
    Tutorial 8
    Tutorial 9
    Tutorial 10
    Tutorial 11
    Tutorial 12