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)


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 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

  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.