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