This course is an advanced study that follows Data Structures and Algorithms. It is designed to equip students with a deep understanding of major algorithmic design paradigms and the techniques required for their rigorous analysis. The curriculum covers the formal analysis of algorithm correctness, time complexity, and space complexity, as well as computational complexity theory including NP‑completeness.
Summer Term course meant for people who want to improve their course grade.
Data Structures and Algorithms (CS F213) or equivalent. Working knowledge of programming in C/C++ or Python.
Textbooks
- (T1) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd Ed., MIT Press (2010).
Reference Books
- (R1) Jon Kleinberg, Eva Tardos. Algorithm Design, Pearson (2012).
- (R2) E. Horowitz, S. Sahni, S. Rajsekaran. Fundamentals of Computer Algorithms, Universities Press.
- (R3) R. Motwani, P. Raghavan. Randomized Algorithms, Cambridge University Press (1995).
- (R4) G. Ausiello et al. Complexity and Approximation, Springer.
Instructor: Tulasimohan Molli
Lectures: Tuesdays, Thursdays 2:00 PM to 3:50 PM, Fridays 4:00 PM to 5:50 PM
Venue: F-206 (TP-Room)
Chamber Consultation Hour: 2 PM on Friday.
| In‑class Evaluation |
10‑15 min surprise quizzes |
10% |
Best 10 of 12‑15 quizzes |
| Assignments (2) |
Take‑home + viva |
20% |
One before mid, one after |
| Midterm Exam |
90 min (closed book) |
30% |
20/06/2026 |
| Comprehensive Exam |
3 h (closed book) |
40% |
15/07/2026 |
- Assignments & in‑class: no make‑up.
- Midterm: case‑by‑case with approval.
- Comprehensive: as per university guidelines.
- Strict adherence to Academic Honesty required; violations will be penalised.
All announcements via Google Classroom or email.
| Lecture 1 |
2026-05-21 |
Introduction to Algorithms |
 |
| Lecture 2 |
2026-05-21 |
Introduction to Sorting & Asymptotic Analysis |
|
| Lecture 3 |
2026-05-21 |
Asymptotic Notation & Merge Sort |
|
| Lecture 4 |
2026-05-21 |
Solving Recurrences |
|
| Lecture 5 |
2026-05-21 |
Divide and Conquer: Maximum Subarray |
|
| Lecture 6 |
2026-05-21 |
Closest Pair of Points in 2D |
|
| Lecture 7 |
2026-05-21 |
Sorting Lower Bounds & Quicksort |
|
| Lecture 8 |
2026-05-21 |
Probability Primer & Randomized Quicksort |
|
| Lecture 9 |
2026-06-02 |
Selection: Randomized & Deterministic |
|
| Lecture 10 |
2026-06-02 |
Dynamic Programming: Fibonacci & LCS |
|
| Lecture 11 |
2026-06-04 |
Matrix Chain Multiplication |
|
| Lecture 12 |
2026-06-04 |
Graphs & Dynamic Programming on Trees |
|
| Lecture 13 |
2026-06-05 |
Greedy: Interval Scheduling |
|
| Lecture 14 |
2026-06-05 |
Huffman Coding |
|
| Lecture 15 |
2026-06-09 |
Minimum Spanning Trees |
|
| Lecture 16 |
2026-06-09 |
MST Algorithms |
|
| Lecture 17 |
2026-06-11 |
Matroids |
|
| Lecture 18 |
2026-06-11 |
Matroids: Greedy Optimization |
|
| Lecture 19 |
2026-06-30 |
Average Case Analysis |
|
| Lecture 20 |
2026-07-02 |
Amortized Analysis |
|
| Lecture 21 |
2026-07-07 |
Further Amortized Analysis |
|
| Lecture 22 |
2026-07-07 |
Network Flow |
|
| Lecture 23 |
2026-07-09 |
Max-Flow Min-Cut Theorem & Ford-Fulkerson |
|
| Lecture 24 |
2026-07-09 |
Bipartite Matching via Max-Flow |
|
| Lecture 25 |
2026-07-10 |
Randomized Algorithms |
|
| Lecture 26 |
2026-07-10 |
Models of Computation & Reductions |
|
| Lecture 27 |
2026-07-11 |
NP-Completeness: Reductions in Action |
|
| Lecture 28 |
2026-07-11 |
Coping with NP-Hardness: LP Relaxation & Rounding |
|
| 1‑5 |
Analyze efficiency via growth‑of‑function and asymptotic notations. |
Asymptotic Analysis, Recurrences |
T1: Ch 1-3 |
| 6‑9 |
Sorting lower bounds, randomized algorithms. |
D&C, Quicksort, Selection |
T1: Ch 4, 7-9 |
| 10‑11 |
Formulate and solve DP problems. |
Dynamic Programming |
T1: Ch 15 |
| 12‑17 |
Greedy strategies, matroids, MST. |
Greedy, Matroids, MST |
T1: Ch 16, 23 |
| 18‑21 |
Average-case and amortized analysis. |
Amortized Analysis |
T1: Ch 17 |
| 22‑26 |
Network flow modelling. |
Network Flow |
T1: Ch 26 |
| 27‑33 |
Complexity classes and NP-Completeness. |
Randomization, P, NP, NP-C |
T1: Ch 5, 34 |
| 34‑37 |
Hard problem techniques. |
Backtracking, B&B, Approx. |
T1: Ch 35, R2, R4 |
| 38‑40 |
Linear Programming. |
Linear Programming |
T1: Ch 29 |
Due: TBA | Weight: 10% | Submission: Individual
Big-Oh, Big-Theta, Big-Omega — comparing growth rates. 4 problems.
Substitution method, Master theorem, two-variable recurrences. 5 problems.
Merge sort variants, missing integer, MST, convex polygon, matrix search. 7 problems.
Interval scheduling, interval stabbing, cookie assignment, knapsack. 5 problems.
String interleaving, petrol pump stops, subset sum. 3 problems.
Post-Midsem Topics
Independence axioms, matroid properties, greedy on weighted matroids. 4 problems.
Aggregate/potential/accounting methods, binary counter, dynamic table variants. 6 problems.
Ford-Fulkerson, max-flow min-cut, edge-disjoint paths, project selection, flow properties. 5 problems.
Las Vegas vs Monte Carlo, dot-product lemma, Freivalds. 3 problems.
P vs NP, 3-SAT to CLIQUE, Vertex Cover, Independent Set reductions. 5 problems.
LP/IP formulation, LP relaxation, Vertex Cover rounding, integrality gap. 3 problems.