• HOME
  • TEACHING
  • NOTES
  • CONTACT
  • LINKS

Algorithms

Logistics

  • Classroom and Time
    1201, D-Slot (Mon 11:00-12:00, Thu 09:00-10:00, Fri 10:00-11:00)
  • TAs
    • Mrityunjay Singh
    • Amit Kumar Srivastava
    • S Vignesh
    • Siddhartha Das
    • Sumit Garg
    • Sandeep A G
  • Textbook
    Algorithm Design Jon Kleinberg, Eva Tardos
  • Evaluation
    Midsem 30, Endsem 40, Quizzes+Class Performance 30, Relative grading.
    Cheating implies F. In addition, all cheating cases will be referred to academic affairs for further action.

Lectures

  • Lecture 01 (Dec 29)
  • We introduced 7representative problems. Interval Scheduling, Weighted Interval Scheduling, Bipartite Matching, Closest Pair of Points, Maximum Independent Set, Max SAT, 7/8-MaxSAT
  • Lecture 02 (Jan 01)
  • Stable Marriage Problem and Gale Shapley Algorithm.
  • Lecture 03 (Jan 02)
  • Stable Matching uniqueness argument. Euclid's algorithm.
  • Lecture 04 (5 Jan)
  • Intro to greedy algorithms. Huffman coding.
  • Lecture 05 (8 Jan)
  • Proof for optimality of Huffman coding. Implementation of Huffman coding.
  • Lecture 06 (9 Jan)
  • Graph algorithms. Representing graphs using adjacency lists and matrices. Introduction to graph traversal.
  • Lecture 07 (19 Jan)
  • Graph traversal. BFS, DFS. Spanning tree and MST definition.
  • Lecture 08 (22 Jan)
  • MST properties. Cut property. Cycle property. Kruskal's algorithm.
  • Lecture 09 (23 Jan)
  • Implementing Kruskal's algorithm. Intro to union find data structures.
  • Lecture 10 (28 Jan)
  • Union find data structures. Amortized analysis.
  • Lecture 11 (2 Feb)
  • Analysis of union find data structures with union by rank and path compression.
  • Lecture 12 (4 Feb)
  • Interval scheduling problem. Divide and conquer paradigm. Intuition to Master's theorem.
  • Lecture 13 (5 Feb)
  • Closest pair of points. Algorithm, correctness and running time analysis.
  • Lecture 14 (6 Feb)
  • Fast integer multiplication. Fast Fourier transforms and polynomial multiplication.
  • Lecture 15 (9 Feb)
  • Review of FFT and reconstructing the polynomial. Quiz.
  • Lecture 16 (12 Feb)
  • Fast exponentiation. Generating Fibonacci numbers. Convex hull.
  • Lecture 17 (13 Feb)
  • Introduction to Dynamic Programming
  • Lecture 18 (16 Feb)
  • Weighted Interval Scheduling, Knapsack Problem

Announcements

  • Practice Problems Uploaded here.
  • First meeting will be on 29th December (11:00-12:00, Room 1201)
Last modified: Tue Feb 17 16:33:26 IST 2015