COL351: Analysis and Design of Algorithms


Announcement: The course is open only for CSE students. For students from other departments, this course will be floated in even semester.

Course Information

Instructor: Keerti Choudhary

Lecture Timing: Tues, Wed, Fri   9:00-10:00 AM   (Slot D)

Tutorial Timing: Mon, Tues, Thurs, Fri   2:00-3:00 PM

Reference Books:
Algorithm Design by Jon Kleinberg and Eva Tardos
Algorithms by Dasgupta, Papadimitriou, and Vazirani

TAs: Chirag Bansal (cs5180402@cse.iitd.ac.in), Kashish Jain (jcs212259@csia.iitd.ac.in), Ronak Ladhar (mcs212146@cse.iitd.ac.in), Sourav Sharma (mcs212154@cse.iitd.ac.in), Surbhi Rajput (csy227519@cse.iitd.ac.in), Lakshay Saggi (csz228231@cse.iitd.ac.in).

Logistics

Evaluation: The course evaluation policy is:

  • Assignments - 20%
  • Exams - 30% + 35%
  • Quizzes - 10%
  • Attendance - 5%

Acadmic Honesty: Cheating or allowing anyone to copy in exams/assignments would lead to strict disciplinary action.

Course Content


Lec. No. Topic Further reading
01 Introduction (O(), Omega(), Graphs, Course Policy)
02 Job Scheduling
03 2-Approximate Vertex Cover
04 Minimum Spanning Tree, Reverse Delete algorithm, Incremental approach
05 Union Find, Kruskal’s MST algorithm, Prim's MST algorithm Union Find in O(log* n) Time
06 Huffman Encoding Length-limited Huffman encoding
07 DFS, Computing Brdiges in a graph
08 DFS applications: Topological ordering, Unique Path Graph problem
09 Computing SCCs in digraphs
10 Quiz
11 Longest Common Subsequence, Matrix Chain Multiplication
12 Longest Increasing Subsequence An alternate O(n log n) time algorithm
13 Pattern Matching (KMP Algorithm)
14 Pattern Matching (contd..)
15 Bellman-Ford Algorithm (Single-source shortest-path) Near linear time algorithm for SSSP
16 Floyd-Warshall Algorithm, Johnson's Algorithm (All-pairs shortest-path)
17 Problem Session
18 Hashing, Modular Airthmetic
19 Quiz, Modular Airthmetic (contd.)
20 Universal Hash family
21 Perfect Hashing, Pattern Matching (intro.) About Prime Number Theorem
22 Rabin-Karp Algorithm for Pattern Matching
23 Minor exam discussion
24 Deterministic and Randomized Quick Sort
25 Minimum Pairwise Distance
26 Polynomial Multiplication Recent results on Integer Multiplication
27 Polynomial Multiplication (contd.), Discrete Fourier Transform Number Theoretic Transform (DFT over Zp)
28 Matrix Multiplication, Transitive Closure
29 Master’s Theorem
30 Network Flow, Residual Graph
31 Ford-Fulkerson Algorithm, (s,t)-cuts
32 Ford-Fulkerson Algorithm (contd.), Max-Flow Min-Cut Theorem
33 Edmonds-Karp Algorithm
34 Polynomial-Time Reductions
35-36 P, NP, and NP-Completeness
37 Approximation Algorithms
38 Quiz