CS21003 Algorithms I - Spring 2021


Instructor: Prof. Partha Pratim Chakrabarti and Palash Dey

Teaching Assistants: Ishan (ish.ranga11@gmail.com), Sourav Saha (sourav.saha@iitkgp.ac.in), Ayush Mahajan (mahajan20june@gmail.com), Abhishek Shaw (abhishekshaw21@iitkgp.ac.in), Paritosh Sinha (psiit@iitkgp.ac.in), Manad Mishra (manadmishra98@gmail.com), Arijit Kar (arijit.kar14@iitkgp.ac.in)

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 (4-5:30 PM)

Grading:
Announcements:
Assignments:

Lectures:
Week 1 Jan 4 PD Introduction -- --
Jan 5 PPC Recursive Problem Formulation and Algorithm Design Lecture Part 1, Lecture Part 2 Slides 1, Slides 2
Jan 7 PD Time Complexity Analysis Lecture, Reference: Chapter 2 of KT book and this Board work (Offline), Board work (Class)
Week 2 Jan 11 PPC Recursions, Efficient Algorithm Design and Analysis Lecture Slides
Jan 12 PD Solving Recurrence Relations Lecture, Chapter 4 of CLRS book and Chapter 1 of JE book Board work (Offline), Board work (Class)
Jan 14 PD+PPC Tutorial 1 Tutorial 1 --
Jan 16
Week 3 Jan 18 PPC Recursions, Efficient Algorithm Design and Analysis cont. Lecture Slides
Jan 19 PPC Divide and Conquer Technique Lecture Part 1, Lecture Part 2, Lecture Part 3 Slides 1, Slides 2, Slides 3
Jan 21 PD+PPC Tutorial 2 Tutorial 2 --
Jan 23
Week 4 Jan 25 PPC Divide and Conquer Technique Lecture Slides
Jan 26 -- Institute Holiday (Republic Day) -- --
Jan 28 PD Greedy Algorithms: Storing Files on Tape Lecture, Reference: JE book Board work (Offline), Board work (Class)
Jan 30 -- First Class Test -- --
Week 5 Feb 1 PD Greedy Algorithms: Activity Selection Lecture, Reference: JE book Board work (Offline), Board work (Class)
Feb 2 PD Greedy Algorithms: Huffman Code Lecture, Reference: JE book Board work (Offline), Board work (Class)
Feb 4 PD+PPC Tutorial 3 Tutorial 3 --
Feb 6 PD+PPC Doubt Clearing Session Class Test 1 Solutions --
Week 6 Feb 8 PPC Dynamic Programming I Lecture Slides
Feb 9 PPC Dynamic Programming II Lecture Slides
Feb 11 PD+PPC Tutorial 4 Tutorial 4 --
Feb 13 PD+PPC Doubt Clearing Session Assignment 1 Solutions --
Week 7 Feb 15 PD Tree, Binary Tree Lecture Board work (Offline), Board work (Class)
Feb 16 -- Institute Holiday (Saraswati Puja) -- --
Feb 18 PD Binary Search Tree Lecture Board work (Offline) Board work (Class)
Feb 20 -- Second Class Test -- --
Week 8 Feb 22 PPC Heaps and Heapsort Lecture Slides
Feb 23 -- Class Suspension (Convocation) -- --
Feb 25 PPC Priority Queues Lecture Slides
Feb 27 -- No Class (Spring break) -- --
Week 9 March 1 -- No Class (Spring break) -- --
March 2 -- No Class (Spring break) -- --
March 4 PPC Priority Queues cont. Lecture --
March 6 PD+PPC Tutorial 5 and Doubt clearing session Tutorial 5 --
Week 10 March 8 PD AVL Tree Lecture Board work (Offline) Board work (Class)
March 9 PD Lower Bounds Lecture, Reference: CLRS and this Board work (Offline), Board work (Class): part 1, part 2
March 11 PD+PPC Tutorial 6 Tutorial 6 --
March 13 PD+PPC Solution Discussion -- --
Week 11 March 15 PD Hash Table Lecture Board work (Offline) Board work (Class)
March 16 PD Selection in O(n) Worst Case Time Lecture Board work (Offline) Board work (Class)
March 18 PD+PPC Tutorial 7 Tutorial 7 Board work
March 20 -- Third Class Test -- --
Week 12 March 22 PPC Introduction to Graphs Lecture Slides
March 23 PPC Graph Traversals Lectures: part 1, part 2 Slides 1, Slides 2
March 25 PPC Graph Traversals cont.
March 27 PD+PPC Tutorial 8 and Doubt Clearing Tutorial 8 --
Week 13 March 29 -- Institute Holiday (Holi) -- --
March 30 PPC Minimum Spanning Trees, Shortest Paths in a Graph Lectures: part 1, part 2 Slides 1, Slides 2
April 1 PPC All Pairs Shortest Paths in a Graph Lecture Slides
April 3 PD+PPC Tutorial 9 and Doubt Clearing Tutorial 9 --
Week 14 April 5 PD+PPC String Matching Lecture Board work (Offline) Board work (Class)
April 6 PD+PPC Disjoint Set Data Structure Lecture Board work (Offline) Board work (Class)
April 8 PD+PPC Tutorial 10 and Doubt Clearing Tutorial 10 --
April 10 PD+PPC Class Test 4 -- --


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.