Design and Analysis of Algorithms (CS301)
Anup Bhattacharya
Anup Bhattacharya
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 Jeffe Erickson
Grading: Class tests: 25%, Mid-Sem: 30%, End-Sem: 40%, Class participation: 5%
Practice Problems: Link (Note that many of these problems are sourced from different places).
Lectures:
Week 1 (08/08/2022 - 12/08/2022): Introduction and Divide and Conquer algorithms
Lec 1 (10/08/2022): Introduction, Computing Fibonnaci numbers (Section 0.2 in DPV)
Lec 2 (11/08/2022): Fibonacci numbers, Mergesort (Section 0.2, 2.3 in DPV)
Lec 3 (12/08/2022): Recurrence relations, Mergesort (Section 2.2 in DPV)
Week 2 (15/08/2022 - 19/08/2022): Divide and Conquer algorithms
Lec4 (16/08/2022): Randomized Select (Section 2.4 in DPV)
Lec5 (17/08/2022): Randomized Quicksort (Section 2.2, 2.4 in DPV)
Lec6 (19/08/2022): Master theorem, Polynomial multiplication (Section 5.1 KT, Section 2.1, 2.2 in DPV)
Week 3 (22/08/2022 - 26/08/2022): Graph algorithms
Lec 7 (24/08/2022): Finish polynomial multiplication, Start graph algorithms (Chapter 3 of DPV, Chapter 3 in KT)
Lec 8 (25/08/2022): Graphs algorithms: BFS, DFS (Chapter 3 of DPV, Chapter 3 in KT)
Lec 9 (26/08/2022): Graph algorithms: Applications of BFS, DFS (Chapter 3 of DPV, Chapter 3 in KT)
Week 4 (29/08/2022 - 02-09-2022): Graph algorithms
Lec 10 (01/09/2022): Topological sort (Chapter 3 of DPV, Chapter 3 in KT)
Lec 11 (02/09/2022): Topological sort (Chapter 3 of DPV, Chapter 3 in KT)
Lec 12 (02/09/2022): Finding strongly connected components (Chapter 3 of DPV, Chapter 3 in KT)
Week 5 (05/09/2022 - 09/09/2022): Greedy algorithms
Lec 13 (07/09/2022): Greedy algorithms for scheduling (Chapter 4 in KT, Section 4.1)
Lec 14 (08/09/2022): Interval scheduling (Chapter 4 in KT, Section 4.1)
Lec 15 (09/09/2022): Scheduling to minimize lateness ((Chapter 4 in KT, Section 4.2)
Week 6 (12/09/2022 - 16/09/2022): Greedy algorithms
Lec 16 (14/09/2022): Finish minimizing lateness for scheduling, Shortest paths in Graphs (Section 4.2 in KT)
Lec 17( 15/09/2022): Dijkstra's algorithm, Examples (Section 4.4 in KT)
Lec 18 (16/09/2022): Correctness of Dijkstra's algorithm (Section 4.4 in KT)
Week 7 (19/09/2022 - 23/09/2022): Greedy algorithms
Lec 19 (21/09/2022): Minimum spanning tree (Section 4.5 in KT)
Lec 20 (22/09/2022): Minimum spanning tree (Section 4.5 in KT)
Lec 21 (23/09/2022): Hoffman Encoding (Section 4.8 in KT)
Mid-semester break
Week 8 (10/10/2022 - 14/10/2022): Dynamic programming
Lec 22 (12/10/2022): Weighted interval scheduling (Section 6.1 in KT )
Lec 23 (13/10/2022): Shortest paths in DAGs, Edit Distance (Section 6.6 in KT, Section 6.3 in DPV)
Lec24 (14/10/2022): Subset Sum (Section 6.4 in KT)
Week 9 (17/10/2022 - 21/10/2022): Dynamic programming
Lec 25 (19/10/2022): Chain Matrix Multiplication (Section 6.5 in DPV)
Lec 26 (20/10/2022): Shortest paths with negative edges (Section 6.8 in KT)
Lec 27 (21/10/2022): Discussed solutions for problems in minor exams
Week 10 (24/10/2022 - 28/10/2022): Network flows
Lec 28 (26/10/2022): Network flows (Section 7.1 and 7.2 in KT)
Lec 29 (27/10/2022): Network flows (Section 7.1 and 7.2 in KT)
Lec 30 (28/10/2022): Network flows (Section 7.1 and 7.2 in KT)
Week 11 (31/10/2022 - 04/11/2022): Flows and LP
Lec 31 (02/11/2022): Bipartite matching using flows (Section 7.5 in KT)
Lec 32 (03/11/2022): Introduction to LPs (Section 7.1 in DPV)
Lec 33 (04/11/2022): LP Duality (Section 7.4 in DPV)
Week 12 (07/11/2022 - 11/11/2022): Flows and LP
Lec 34 (09/11/2022): Applications of Flows (Section 7.7 in KT)
Lec 35 (10/11/2022): Zero-sum Games (Section 7.5 in DPV)
Lec 36 (11/11/2022): Class test 2
Week 13 (14/11/2022 - 18/11/2022):
Lec 37 (16/11/2022): Discuss solutions of class test 2
Lec 38 (17/11/2022): Complete LP formulations for zero-sum games, Introduce Computational Hardness
Lec 39 (18/11/2022): Polynomial time reductions (Section 8.1, 8.2 in KT)
Week 14 (21/11/2022 - 25/11/2022):
Lec 40 (23/11/2022): NP, NP-complete Problems (Section 8.3, 8.4 in KT)