# CS21003 Algorithms I - Spring 2022

Instructor: Prof. Partha Pratim Chakrabarti and Palash Dey

Teaching Assistants: Amatya Sharma, Manasvi Sagarkar, Chandan Kumar, Sayani Sinha, Debadrita Talapatra, and Manjish Pal

Course overview:
Asymptotic notations and their significance, introduction to RAM model of computation, complexity analysis of algorithms, worst case and average case. Basic introduction to algorithmic paradigms like divide and conquer, recursion, greedy, etc. Searching: binary search trees, balanced binary search trees, AVL trees and red-black trees, B-trees, skip lists, hashing. Priority queues, heaps, Interval trees, tries. Order statistics. Sorting: comparison based sorting - quick sort, heap sort, merge sort: worst and average case analysis. Decision tree model and (worst case) lower bound on sorting. Sorting in linear time - radix sort, bucket sort, counting sort, etc. String matching Graph Algorithms: BFS, DFS, connected components, topological sort, minimum spanning trees, shortest paths - single source and all pairs.

Classes: Monday (12:00–12:55), Tuesday (10:00–11.55), Thursday (08:00–08:55) [Slot D4], Saturday (6-7:30 PM)

• Midterm and Endterm: 50%
• Class test: 20% (2 class tests; best 1 out of 2)
• Assignment: 10% (4 assignments; best 2 out of 4)
• Attendance and teachers’ evaluation: 10%
• Students' Presentation: 10%
• Submit initial problem statement by January 24 (Monday)
• Finalize problem statement by January 31 (Monday)
• Format of presentation: Motivation, formal problem definition with clear input and output specification, pseudocode of the algorithm, analysis of the algorithm, implementation of the algorithm in C/C++ programming language.
• Group size is 2-3. In the video presentation, every member of the group should speak for an equal duration of time.
• You need to submit 4 things: (i) video of the presentation, (ii) slides of the presentation, (iii) C/C++ code, and (iv) a readme.txt file clearly explaining how to compile and execute your code. Share a folder containing these on Google Drive.
• Duration of presentation: 15-20 minutes

Announcements:
• Link to last year's classes: here
• Class test 1 is scheduled on January 29 at 6 PM.

Assignments:
• Assignment 1 is here. Submit on MS Teams. Deadline is 11:59 PM on January 26, 2021. Solution sketch of Q1, 2, and 3 is here.

Lectures:
 Week 1 Jan 10 PPC Recursive Problem Formulation and Efficient Algorithm Design Slides Jan 11 Slides: this and this Jan 13 PD Analysis of Algorithm Board work Jan 15 PD Solving Recurrence Relations Board work Week 2 Jan 17 PPC Recursions, Efficient Algorithm Design and Analysis Slides Jan 18 PPC Divide and Conquer Slides Jan 20 PD+PPC Tutorial 1 Tutorial 1 Jan 22 Week 3 Jan 24 PPC Divide and Conquer Technique Slides Jan 25 PPC Divide and Conquer Technique Slides: this and this Jan 27 Jan 29 First Class Test

References:
1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
2. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
3. Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.
4. Jeff Erickson, Algorithms, 2019.
5. Mark Allen Weiss, Data Structures and Algorithm Analysis in C.