CS21003 Algorithms I - Spring 2022

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)

Grading:

Endterm: 30%
Class test: 40% (2 class tests and 1 mid term; best 2 out of 3)
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)
Deadline for uploading presentation: March 31 EOD
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.
Mid-term is scheduled on February 22 at 10 AM.
Class test 2 is scheduled on March 26 at 6 PM.
End-term is scheduled on April 12 at 11 AM in MS Teams.

Assignments:

Assignment 4 is here. Submit on MS Teams. Deadline is 11:59 PM on April 6, 2022.
Assignment 3 is here. Submit on MS Teams. Deadline is 11:59 PM on March 22, 2022. Solution sketches of Q2 and Q3 are here.
Assignment 2 is here. Submit on MS Teams. Deadline is 11:59 PM on February 17, 2022. Solution sketch of Q1 is here.
Assignment 1 is here. Submit on MS Teams. Deadline is 11:59 PM on January 26, 2022. 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	PPC		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	PD+PPC	Tutorial 1	Tutorial 1
Week 3	Jan 24	PPC	Divide and Conquer Technique	Slides
	Jan 25	PPC	Divide and Conquer Technique	Slides: this and this
	Jan 27	PPC	Divide and Conquer Technique	Slides: this and this
	Jan 29	First Class Test		Questions: Part 1, Part 2 Solution sketches: Part 2
Week 4	Jan 31	PD	Greedy Algorithm: Job Scheduling	Board work
	Feb 1	PD	Greedy Algorithm: Huffman Coding	Board work
	Feb 3	PD	Tutorial 2	Tutorial 2
	Feb 5	PPC	Tutorial 3	Tutorial 3
Week 5	Feb 7	PPC	Dynamic Programming: Matrix Chain Multiplication	Slides
	Feb 8	PPC	Dynamic Programming: String Matching, LCS, Edit Distance	Slides
	Feb 10	PPC	Tutorial 4	Tutorial 4
Week 6	Feb 14	PD	Tree, Binary Search Tree	Board work
	Feb 15	PD	Binary Search Tree, AVL Tree	Board work
	Feb 17	PD	Tutorial 5	Tutorial 5
Week 7	Feb 21	--	No Class (Midsemester break)	--
	Feb 22	Mid-semester Examination		Questions: Part 1, Part 2 Solution sketches: Part 2
	Feb 24	--	No Class (Midsemester break)	--
Week 8	Feb 28	--	No Class (Kshitij)	--
	Mar 1	PPC	Heap, Heap Sort, and Pririty Queue	Slides: this and this
	Mar 3	PPC	Tutorial 6	Tutorial 6
Week 9	Mar 7	PD	Lower bounds	Board work, Reference
	Mar 8	PD	Linear Time Selection	Board work
	Mar 10	PD	Tutorial 7	Tutorial 7
Week 10	Mar 14	PD	Hashing	--
	Mar 15	PPC	Graph and Graph Traversals	Slides: this and this
	Mar 17	PPC	Traversal of Directed Graphs	Slides
	Mar 19	PD+PPC	Tutorial 8	Tutorial 8
Week 11	Mar 21	PPC	Minimum Spanning Tree	Slides
	Mar 22	PPC	Shortest Path	Slides: this and this
	Mar 26	PPC	Tutorial 9	Tutorial 9
	Mar 26	Second Class Test		Questions: Part 1, Part 2 Solution sketches: Part 1
Week 12	Mar 28	PD	Disjoint Set Union-Find Data Structure	Board work
	Mar 29	PD	String Matching	Board work
	Mar 31	PD	Tutorial 10	Tutorial 10
	April 12	End Semester Examination		Questions: Part 1, Part 2 Solution sketches: Part 1

References:

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