COL351: Analysis and Design of Algorithms

Announcement: The course is open only for (i) Non-CSE students of 2022 or earlier entry, and (ii) CSE students of 2021 or earlier entry.

Course Information

Lecture Timing: Mon, Thurs 8:00-9:30 AM (Slot A), LH 416

Tutorial Timing: Mon, Tues, Thurs, Fri 1:00-2:00 PM, LH 521

Reference Books:
Algorithm Design by Jon Kleinberg and Eva Tardos
Algorithms by Dasgupta, Papadimitriou, and Vazirani
Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein
Algorithhms by Robert Sedgewick, Kevin Wayne

TAs: Samyak Jain (cs5200667@cse.iitd.ac.in), Jatin Yadav (csz237549@cse.iitd.ac.in), Rittik Dey (csz248007@cse.iitd.ac.in), Shivansh Garg (mcs242450@cse.iitd.ac.in)

Logistics

Evaluation: The course evaluation policy is:

Exams - 35% + 40%
Surprise quizzes - 15%
Class participation - 5% (Lec) + 5% (Tut)

Passing criteria: 30% in course total

Audit-pass criteria: 45% in course total

Acadmic Honesty: Cheating or allowing anyone to copy would lead to a penalty of one grade per quiz / exam.

Course Content

Lec. No.	Topic	Further reading
01	Introduction, Algorithmic paradigms (Divide and conquer, Dynamic programming, Greedy algorithms)
02	Interval Selection Problem
03	Minimum Spanning Tree, Reverse Delete algorithm, Kruskal's MST algorithm
04	Kruskal's MST algorithm (contd.), Union-Find data-structure, Prims algorithm	Union-Find in O(log* n) Time
05	Huffman Encoding	Length-limited Huffman encoding
06	Weighted Interval Selection, Longest Common Subsequence, Partitioning Problem
07	Dynamic Programming on Trees, Quiz-1
08	Dynamic Programming on Trees (contd.), Strategy games	Coins in a Row Game: Optimal solution
09	Longest Increasing Subsequence
10	Knuth-Morris-Pratt (KMP) algorithm for pattern matching
11	Order Satistics, Deterministic Quick Sort, Minimum Pairwise Distance
12	Quiz-2
13	Minimum Pairwise Distance (contd.), Randomized Quick Sort, Randomized Order Satistics
14	Quiz discussion, Divide and Conquer on Trees
15	Bellman-Ford Algorithm, Floyd-Warshall Algorithm	Near linear time algorithm for SSSP
16	Matrix Multiplication, All-Pairs Reachability, All Pairs 2-Approximatie Distance Computation
17	DFS, Kosaraju's SCC algorithm, Topological Sort
18	Unique Path Graph problem, Computing Brdiges in a graph
19	Network flows, Ford-Fulkerson Algorithm
20	(s,t)-cuts, Max-Flow Min-Cut Theorem, Optimality of Ford-Fulkerson Algorithm
21	Quiz-3, Modular airthmetics
22	Rabin-Karp Algorithm
23	Polynomial multiplication
24	Polynomial multiplication (contd.), Polynomial-Time Reductions
25	P, NP, and NP-Completeness, Cook-Levin's theorem
26	NP-Completeness of 3SAT, Set Cover, Hitting Set
27	Quiz-4
28	Coping with NP-completeness