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