Design and Analysis of Algorithms

Announcements:

• Unfortunately, because of the prevailing pandemic due to covid-19, we have decided to end the lectures for the Algorithms course for the second semester, 2020. There will not be any further lectures or assignments on topics of this course. We could not cover some topics for this course. We recommend students taking a look at the last year's web page for the course here, in particular, from Lecture 32 to Lecture 37. We consider these topics to be fundamental for a course like this. Since, we could not cover it ourselves, we recommend students reading the materials listed above or watching videos like these to get a sense of these topics.
• Quiz 2 is announced. Please find the questions here (pdf) and here (tex).
• The second programming assignment is out, the submission deadline is 15/04/2020.
• Sample solution for quiz 1 is here.
• The first programming assignment is out, the submission deadline is 21/02/2020. Please find the assignment here.
• There will be a quiz on Monday (10/02/2020): Syllabus: basic data structures arrays, linked lists, binary trees, heaps, stack and queues, binary search, sorting algorithms, basic lower bound techniques, recurrence relations, BFS, proof of correctness of algorithms and determining running time.

References: We mention below a list of books that you may follow for this course. Also, there are numerous lecture notes available on the web.

1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein (CLRS), Introduction to Algorithms, Second Edition, MIT Press/McGraw-Hill, 2001.
2. Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani (DPV), Algorithms, Tata McGraw-Hill, 2008.
3. Jon Kleinberg and Éva Tardos (KT), Algorithm Design, Pearson, 2005.
4. A good set of slides on related topics can be found here.
5. An excellent set of lecture notes on algorithms is here (notes available online).

Grading: Mid-Sem 25%, End-Sem 50%, Assignments 20% (Quizzes & Programming exercises)

We will be updating a problem set periodically for you to work on. You need not submit solutions for these problems, some of these problems will be discussed during the tutorial sessions.

Lectures:

1. Lecture 1 on 20/01/2020 (Anup): Introduction, Computation of GCD and Euclid's algorithm.
2. Lecture 2 on 22/01/2020 (Sourav): Finding max and second max, binary search and lower bound ideas.
3. Lecture 3 on 27/01/2020 (Anup): We covered insertion sort, merge sort and introduced quick sort. Materials for this lecture are from CLRS.
4. Lecture 4 on 29/01/2020 (Anup): We covered randomized quicksort, randomized selection and lower bound for comparison-based sorting algorithms. [CLRS]
5. Tutorial 1 on 31/01/2020 (Sayantan):
6. Lecture 5 on 03/02/2020 (Anup): We covered counting sort, radix sort and bucket sort algorithms. [CLRS]
7. Lecture 6 on 05/02/2020 (Sourav): We started talking about graph traversal algorithms, in particular BFS.
8. Tutorial 2 on 07/02/2020 (Sayantan):
9. Quiz 1 on (10/02/2020):
10. Lecture 7 on 12/02/2020 (Sourav): We discussed DFS algorithm for graph traversal and topological sort.
11. Lecture 8 on 12/02/2020 (Sourav): We started discussing minimum spanning tree (MST) algorithms. In particular, Prim's and Kruskal algorithms for MST.
12. Lecture 9 on 14/02/2020 (Sourav): We discussed shortest path algorithm in graphs, in particular Dijkstra's algorithm.
13. Lecture 10 on 17/02/2020 (Sourav): Bellman-Ford and Floyd-Warshall algorithms for all pairs shortest paths in graphs.
14. Lecture 11 on 24/02/2020 (Anup): We discussed dynamic programming algorithms for weighted interval scheduling and knapsack. [KT: Sections 6.1, 6.4]
15. Lecture 12 on 26/02/2020 (Anup): We discussed dynamic programming algorithms for matrix chain multiplication [CLRS: 15.2], edit distance [KT: 6.6], and TSP [DPV: 6.6].
16. Lecture 13 on 11/03/2020 (Anup): Introduced max-flow, Ford-Fulkerson [KT]