COL 351 : Analysis and Design of Algorithms
Textbook
    Title : Algorithm Design.
    Authors : Jon Kleinberg and Eva Tardos
Supplementary Text:
      (i) Algorithms, by Dasgupta, Papadimitriou, and Vazirani
      (i) Algorithms, by Jeff Erickson (available online)
   
Lecture Topics
Lecture 1: Introduction, Overview of the course
Lecture 2: Greedy Algorithms. Interval Selection Problem, Exchange Argument. [KT Chapter 4]
Lectrue 3: Exchange argument contd., Minimum Average Completion time. [KT Chapter 4]
Lecture 4: Minimum Spanning Tree and Kruskal's algorithm. [KT Chapter 4]
Lecture 5: Huffman codes [KT Chapter 4]
Lecture 6: Stable Matching [KT Chapter 1]
Lecture 7: Stable Matching, Quiz [KT Chapter 1]
Lecture 8: Divide and Conquer Paradigm, mergesort, quicksort. [KT Chapter 5]
Lecture 9: Randomized Quicksort and randomized selection [KT Chapter 13.5]
Lecture 10: Deterministic Selection [Erickson Chapter 1.8]
Lecture 11: 2D dominating set, Closest Pair [KT Chapter 5]
Lecture 12: Polynomial multiplication and representation, Quiz [DPV Chapter 2.6]
Lecture 13: FFT Algorithm [DPV Chapter 2.6]
Lecture 14: Dynamic Programming, Fibonacci numbers
Lecture 15: 0-1 Knapsack, Weighted Interval Selection [DPV Chapter 6.4, KT Chapter 6.1]
Lecture 16: Maximum Sub-array Sum, Maximum Increasing Subsequence [DPV Chapter 6]
Lecture 17: Longest Common Subsequence, Chain Matrix Multiplication [DPV Chapter 6]
Lecture 18: Shortest Paths in Directed Acyclic Graphs, Quiz [DPV Chapter 6]
Lecture 19: Shortest Paths: Bellman Ford Algorithm
Lecture 20: Shortest Paths: Diskstra's algorithm.
Lecture 21: Shortest Paths: All pairs shortest paths.
Lecture 22: Bipartite Matching: Augmenting Path algorithm.
Lecture 23: Bipartite Matching: Hall's Theorem and Applications, Quiz.
Lecture 24: Max Flow: Residual graphs, Ford-Fulkerson Algorithm
Lecture 25: Max Flow-Min Cut Theorem
Lecture 26: Applications of Max-Flow: Disjoint paths, bipartite matching
Lecture 27: Applications of Max-Flow: Circulation, Demands and Supply
Lecture 28: Applications of Min-Cut: Project Selection Problem
Lecture 29: Applications of Max-Flow: Baseball Elimination Problem, Quiz
Lecture 30: Decision Problems and Optimization Problems, Proof Verification
Lecture 31: Reduction between decision problems
Lecture 32: P vs NP and examples
Lecture 33: NP Completeness and Examples: Vertex Cover, Independent Set, Clique
Lecture 34: NP Completeness and Examples: Subset Sum
Lecture 34: NP Completeness and Examples, Quiz
Lecture Timings
  Tuesday, Wednesday, Friday: 10-11am
  Venue : LH 316
Tutorials
  Timming: Tuesday, Wednesday, Thursday: 1-2 pm, Venue : LH 615.
 
    Tutorial 1
    Tutorial 2
    Tutorial 3
    Tutorial 4
    Tutorial 5
    Tutorial 6
    Tutorial 7
    Tutorial 8
    Tutorial 9
    Tutorial 10
    Tutorial 11
    Tutorial 12