Design and Analysis of Algorithms 

(CS 218)

Schedule: Monday (11:30-12:30 AM), Tuesday (8:30-9:30 AM), Thursday (9:30-10:30 AM). 

Venue:  LA 001

Office hours: Thursday 4-5 PM. 

Course Contents: 

• Algorithms: 

  • Basic principles like induction/recursion. Basic paradigms like Divide and Conquer, Dynamic Programming, Greedy Algorithms. Beyond the basics: Network Flow and its applications. Graph Algorithms. Linear Programming. Reductions.

• Complexity: 

  • Polynomial time and the Complexity classes NP, co-NP. NP-hardness and NP-completeness.

• Advanced Topics:

  • Approximation Algorithms, Randomized Algorithms. Online Algorithms. 

References:  

1. Algorithm Design, John Kleinberg, Eva Tardos. 

2. Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.

3. The Design of Approximation Algorithms, David B. Shmoys and David P. Williamson.

4. Approximation Algorithms, Vijay Vazirani. 

5. Randomized algorithms, Rajeev Motwani and Prabhakar Raghavan. 

6. Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak. 

Lectures: 

• Lecture 1 (5/1/26): Course Introduction. Basics of Algorithm Design. 

• Lecture 2 (6/1/26): Binary search and variants. 

• Lecture 3 (11/1/26): O(·) notation. Analyzing and describing algorithms. Reduction to a subproblem. Maximum subarray sum problem.