Design and Analysis of Algorithms

CS F364 | May-July 2026

Download Course Handout (PDF)

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

  1. (T1) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd Ed., MIT Press (2010).

Reference Books

  1. (R1) Jon Kleinberg, Eva Tardos. Algorithm Design, Pearson (2012).
  2. (R2) E. Horowitz, S. Sahni, S. Rajsekaran. Fundamentals of Computer Algorithms, Universities Press.
  3. (R3) R. Motwani, P. Raghavan. Randomized Algorithms, Cambridge University Press (1995).
  4. (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.

Component Duration / Format Weight Date & Time
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.

# Date Topic Slides
Lecture Learning Objectives Topics Reference
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
Assignment 1

Problems: Problem A | Problem B | Problem C | Problem D

Due: 30 Jun 2026, 2:00 PM  |  Weight: 10%  |  Submission: Individual  |  Final mark: Score (out of 50) × Viva ÷ 10

Assignment 2

Due: TBA  |  Weight: 10%  |  Submission: Individual

Asymptotic Notation

Big-Oh, Big-Theta, Big-Omega — comparing growth rates. 4 problems.

Recurrence Relations

Substitution method, Master theorem, two-variable recurrences. 5 problems.

Divide & Conquer

Merge sort variants, missing integer, MST, convex polygon, matrix search. 7 problems.

Greedy Algorithms

Interval scheduling, interval stabbing, cookie assignment, knapsack. 5 problems.

Dynamic Programming

String interleaving, petrol pump stops, subset sum. 3 problems.

Post-Midsem Topics

Matroids

Independence axioms, matroid properties, greedy on weighted matroids. 4 problems.

Amortized Analysis

Aggregate/potential/accounting methods, binary counter, dynamic table variants. 6 problems.

Network Flow & Matching

Ford-Fulkerson, max-flow min-cut, edge-disjoint paths, project selection, flow properties. 5 problems.

Randomized Algorithms

Las Vegas vs Monte Carlo, dot-product lemma, Freivalds. 3 problems.

NP-Completeness & Reductions

P vs NP, 3-SAT to CLIQUE, Vertex Cover, Independent Set reductions. 5 problems.

LP, IP, Relaxations & Rounding

LP/IP formulation, LP relaxation, Vertex Cover rounding, integrality gap. 3 problems.