Course Number : CS 218

Instructor : Mrinal Kumar

Email : first name AT cse DOT iitb DOT ac DOT in

Lectures: Wed/Fri 11 am-12:30 pm

Office hours: Wed 12:30 pm-1:30 pm

- Roshan Raj (194054001@iitb.ac.in)
- Rajendra (203050094@iitb.ac.in)
- Kushagra Shandilya (kushagras@cse.iitb.ac.in)
- Ashish Aggarwal (ashishaggarwal@cse.iitb.ac.in)
- Abhinivesh (abhinivesh@cse.iitb.ac.in)
- Nilesh Tanwar (203050060@iitb.ac.in)
- Shivam Gautam (213050003@iitb.ac.in)

Grades will be based on two mid-sems (30% + 25% respectively), a final exam (40%) and class participation (5%).

There will be a few problem sets through the course that will not be graded (but are highly recommended).

This is a fairly standard undergraduate course in the design and analysis of algorithms, typically meant for computer science undergraduates. I will assume some familiarity with the material in the class on data structures and algorithms in the previous semester. The course would be largely mathematical, and will involve design of algorithms as well as formal proofs of correctness and bounds on performance of such algorithms.

We will see some of the algorithm design paradigms/techniques and their applications to design algorithms for various computational problems. We will also discuss the notion of computational hardness and see some of the strategies for coping with computational hardness.

We will follow the textbooks by Kleinberg and Tardos and the one by Cormen et al. for a large part of the course. Both these books contain a fairly large number of exercises and I highly encourage you to check them out.

- Jan 05 (Lec 01): Administrivia and getting started.
- Jan 07 (Lec 02): Fast integer multiplication (Karatsuba). Fast matrix multiplication (Strassen).
- Jan 12 (Lec 03): Fast matrix multiplication contd. Fast polynomial multiplication (FFT).
- Jan 14 (Lec 04): Fast polynomial multiplication contd.
- Jan 19 (Lec 05): Dynamic programming: intro, simple examples.
- Jan 21 (Lec 06): Discussion of problem sets 1 and 2.
- Jan 26: No lecture (Republic day).
- Jan 28 (Lec 07): Subset sum, knapsack.
- Feb 02 (Lec 08): Knapsack contd, edit distance.
- Feb 04 (Lec 09): Graphs intro, Dijkstra's algorithm, Bellman-Ford algorithm.
- Feb 09 (Lec 10): Bellman-Ford contd.
- Feb 11 (Lec 11): Discussion of Problem set 3.
- Feb 16 (Lec 12): Bellman-Ford contd, Floyd-Warshall algorithm for APSP.
- Feb 18 (Lec 13): Floyd-Warshall contd, Greedy algorithms: minimum spanning tree.
- Feb 23: No lecture..midsem week.
- Feb 25: No lecture..midsem week.
- Mar 02 (Lec 14): Greedy algorithms: Huffman codes.
- Mar 04 (Lec 15): Huffman codes contd. Flows and cuts: intro.
- Mar 09 (Lec 16): Max flow-min cut.
- Mar 11 (Lec 17): Max flow-min cut contd.
- Mar 16 (Lec 18): Max flow-min cut: applications.
- Mar 18: No lecture...institute holiday.
- Mar 23 (Lec 19): Discussion of problem set 4.
- Mar 25 : Midsem 2.
- Mar 30 (Lec 20): Computational hardness.
- Apr 01 (Lec 21): Computational hardness contd.
- Apr 06 (Lec 22): Approximation algorithms.
- Apr 08 (Lec 23): Exponential time algorithms.
- Apr 13 (Lec 24): Linear programming: intro.
- Apr 15 (Lec 25): Discussion of problem set 5. Summary of the course.