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