Design and Analysis of Algorithms (CS301)

About the course: Computers are everywhere around us, sometimes insides our pockets :). We rely on them a lot in our daily lives for numerous tasks. But, how does a computer actually solve a task? Somebody has to first figure out how to solve that problem and write it up in a manner that a computer can execute. In this course, we will primarily focus on the first part of the above two tasks. Given a problem, how do we solve that problem? How do we ensure the correctness of our solution? Can we design better algorithms for some problem? We will try to answer these questions in this course. At the end of the course, you would become familiar with different algorithm design techniques and arguing about the correctness of the solutions.

References: There are a number of textbooks available on algorithm design and analysis. 

• Algorithms by Dasgupta, Papadimitriou and Vazirani (DPV)

• Algorithm Design by Kleinberg and Tardos, Low Priced Ed. by Pearson (KT), Slides on KT here

• Book and Online Lecture Notes by Jeff Erickson

Grading: Class tests: 30%, Mid-sem: 25%, End-sem: 40%, Class participation: 5%

Practice Problems: Here

Lectures:

Lec 1 (01/08/2023): Introduction, Algorithm for multiplying two numbers

Lec 2 (02/08/2023): Asymptotic notations, Algorithm for multiplying two numbers

Lec 3 (08/08/2023): Recurrence relation for algorithm for multiplying two numbers (Sec 2.1 in DPV)

Lec 4 (09/08/2023): Mergesort, Quicksort, Solving recurrences (Section 2.2, 2.3 in DPV)

Lec 5 (10/08/2023): Choosing pivots, Median finding (Section 2.4 in DPV)

Tutorial 1 (10/08/2023):

Lec 6 (16/08/2023): Graphs, representations, BFS (Section 3.1 in DPV)

Lec 7 (17/08/2023): BFS, Connected components, Introducing DFS (Note here)

Tutorial 2 (17/08/2023):

Lec 8 (22/08/2023): DFS, directed acyclic graphs (Section 3.2 in DPV)

Lec 9 (23/08/2023): Topological sorting, Strongly connected components (Section 3.3 in DPV)

Lec 10 (24/08/2023): Finish algorithm for strongly connected components. Introduce greedy algorithms (Section 3.4 in DPV)

Tutorial 3 (24/08/2023):

Lec 11 (29/08/2023): Greedy algorithms, Scheduling problems (Section 4.1 in KT)

Lec 12 (30/08/2023): Scheduling to minimize lateness (Section 4.2 in KT)

Lec 13 (31/08/2023): Finish greedy algorithm for scheduling, Start Hoffman encoding (Section 4.2 and 4.8 in KT)

Class test 1 (31/08/2023):

Lec 14 (05/09/2023): Hoffman encoding (KT Section 4.8)

Lec 15 (06/09/2023): Shortest paths in graphs, Dijkstra's algorithm (Section 4.4 in KT)

Lec 16 (07/09/2023): Finish Dijkstra's, Start minimum spanning trees (Section 4.4, 4.5 in KT)

Tutorial (07/09/2023):

Lec 17 (12/09/2023): Finish minimum spanning trees (Section 4.5 KT)

Lec 18 (13/09/2023): Lower bounds for sorting (Section 2.3 in DPV)

Lec 19 (14/09/2023): Stable matching (Section 1.1 in KT)

Abhishek's notes on dynamic programming: Notes