- Classroom and Time
1201, D-Slot (Mon 11:00-12:00, Thu 09:00-10:00, Fri 10:00-11:00)
- Mrityunjay Singh
- Amit Kumar Srivastava
- S Vignesh
- Siddhartha Das
- Sumit Garg
- Sandeep A G
Algorithm Design Jon Kleinberg, Eva Tardos
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.
Lecture 01 (Dec 29)
We introduced 7representative problems. Interval Scheduling, Weighted
Interval Scheduling, Bipartite Matching, Closest Pair of Points, Maximum Independent Set, Max SAT,
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)
algorithm. Intro to union find data structures.
Lecture 10 (28 Jan)
Union find data structures.
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
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