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, Quiz 1. [KT Chapter 4]
  • Lecture 6: Huffman codes, Stable Matching [KT Chapter 4, Chapter 1]
  • Lecture 7: Huffman codes [KT Chapter 4]
  • Lecture 8: Stable Matching [KT Chapter 1]
  • Lecture 9: Divide and Conquer paradigm, quicksort [KT Chpater 5], Quiz 2
  • Lecture 10: Randomized Quicksort and randomized selection [KT Chapter 13.5]
  • Lecture 11: Deterministic Selection [Erickson Chapter 1.8]
  • Lecture 12: 2D dominating set, Closest Pair [KT Chapter 5]
  • Lecture 13: Polynomial multiplication and FFT [KT Chapter 5]
  • Lecture 14: Dynamic Programming, 0-1 Knapsack [KT Chapter 6.1], Quiz 3
  • Lecture 15: Weighted Interval Selection [KT Chapter 6.1], Maximum Increasing Subsequence [DPV Chapter 6]
  • Lecture 16: Longest Common Subsequence, Chain Matrix Multiplication [DPV Chapter 6]
  • Lecture 17: Shortest Paths in Directed Acyclic Graphs [DPV Chapter 6], Quiz 4
  • Lecture 18: Shortest Paths: Bellman Ford Algorithm [KT Chapter 6.8], Floyd Warshall Algorithm [DPV Chapter 6]
  • Lecture 19: Dynamic Programming on Trees [DPV Chapter 6], cut vertices in linear time using DFS
  • Lecture 20: Maximum Flow problem, Ford-Fulkerson Algorithm [KT Chapter 7.1]
  • Lecture 21: Max-flow min-cut theorem [KT Chaper 7.2], Maximum matching in bipartite graphs [KT chpater 7.5]
  • Lecture 22: Disjoint paths problem, Project Selection Problem [KT Chpater 7.6, 7.11]
  • Lecture 23: Baseball Elimination Problem, Circulation with demands and lower bounds, Airline Scheduling [KT Chapter 7.12, 7.7, 7.9]
  • Lecture 24: Notion of decision vs optimization problems, vertex cover, Hamiltonian cycle problems [KT Chapter 8], Quiz 5
  • Lecture 25: Polynomial time reductions [KT Chpater 8]

    Lecture Timings

      Monday, Thursday: 8-9:15 am
      Venue : LH 408


    Tutorials

      Timming: Monday, Thursday, Friday : 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
        Tutorial 13

    Grading Policy

    5% Tutorial Attendance (each student must select exactly one day when he/she will attent tutorial -- choice link )
    30% Surprise Quizzes
    30% Mid-term Exam
    35% Major Exam