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