Asymptotic notation , solving recurrences (Chapters 2,3,4 CLRS)
Integer multiplication (Section 1.9, JE)
Matrix multiplication (Section 4.2, CLRS)
Selection in linear time (Section 9.3, CLRS)
Convex Hull (Section 33.3, CLRS)
Van Emde Boas Trees (Chapter 20, CLRS)
Counting inversions (Section 5.3, KT)
FFT (Chapter 30, CLRS)
Storing files on tape (Section 4.1, JE)
Scheduling classes (Section 4.2, JE & Section 16.1, CLRS)
Huffman codes (Section 4.4. JE & Section 16.3, CLRS)
Stable matching (Section 4.5 , JE)
Minimum Spanning Trees (Chapter 23, CLRS)
Matroids (Section 16.4, CLRS)
Insem 1
Introduction to dynamic programming: Fibonacci numbers (Sections 3.1-3.2, JE)
Longest common subsequence (Section 15.4, CLRS)
Edit Distance (Section 3.7, JE)
Matrix Chain Multiplication (Section 15.2, CLRS)
Subset Sum (Section 3.8, JE)
MIS in trees (Section 3.10, JE)
All Pairs Shortest Paths: Floyd Warshall Algorithm (Chapter 9 , JE)
Linear Programming: Simplex algorithm (Chapter 29, CLRS)
Network flows: Ford Fulkerson algorithm (Sections 26.1-26.2, CLRS)
Max flow min cut theorem (Section 10.3, JE)
Applications of flows and cuts: maximizing edge-disjoint and vertex-disjoint paths (Sections 11.1-11.2, JE)
Maximum Bipartite Matching (Section 26.3, CLRS)
Baseball elimination (Section 11.6, JE)
Exam scheduling (Section 11.4, JE)
Insem 2
NP-completeness (Chapter 34, CLRS)
Approximation algorithms- MVC, Eucidean TSP, Set cover, MAX-SAT, Weighted vertex cover (Sections 35.1-35.4, CLRS)
Probabilistic analysis and randomized algorithms ( Chapter 5, CLRS)
Amortized analysis (Chapter 17, CLRS)
Hash tables, dictionary problem (Sections 11.2,11.3,11.5 CLRS )
Checking matrix multiplication: Frievald's algorithm (Section 7.1, MR)
Skip lists (Section 8.3, MR)
Number Theoretic algorithms: GCD, Solving modular equations, Powers of an element (Sections 31.1-31.6, CLRS)
RSA cryptosystem (Section 31.7, CLRS)
Endsem: Full syllabus
References:
(CLRS) Introduction to algorithms, Third edition , Cormen et al
(JE) Algorithms by Jeff Erickson.
(KT) Algorithm design by Kleinberg and Tardos.
(MR) Randomized algorithms by Motwani and Raghavan