Algorithms1  CS21003
Autumn Semester  2019
Instructors
Prof. Animesh Mukherjee will be teaching Section1 (Odd Roll Numbers)
and I will be teaching Section2 (Even Roll Numbers). The Timings below
are same for both the sections, except that the classes for Section1
will be in NR 124.
Course Timings
Lectures
Wednesday  10:00  11:00 (NR424)
Thursday  09:00  10:00 (NR424)
Friday  11:00  12:00 (NR424)
Tutorial: Wednesday  18:00  19:00 (CSE 120)
Lab
Thursday  14:00  17:00 (CIC PC Lab II, PC Lab V)
Teaching Assistants
Rima Hazra, Paramita Das, Binny Mathew, Bishal Santra, Kalyani Roy,
Rajdeep Mukherjee, Soumadip Biswas, Aniruddha Roy, Mayank Bhushan,
Yeredla Shekar Reddy
Reference and Text Books
 Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford
Stein, Introduction to Algorithms, Third Edition, MIT Press,
2009.
 Richard Neapolitan, Foundations of Algorithms, Fifth
Edition, Jones and Barlett Publishers, 2009.
 Udi Manber, Algorithms  A Creative Approach, AddisonWesley,
Reading, MA, 1989.
 Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
Topics Covered
July 17th, 2019 
Introduction: What is an algorithm? 
July 18th, 2019 
Efficiency of Algorithms 
July 19th, 2019 
Complexity Analysis 
July 24th, 2019 
Algorithm Design Techniques: Divide and Conquer, Binary Search, MergeSort 
July 25th, 2019 
Divide and Conquer: QuickSort, Average Case Complexity 
July 26th, 2019 
Divide and Conquer: Matrix Multiplication, Polynomial
Multiplication, Closest Pair of Points 
August 2nd, 2019 
Graph Data Structure: Definitions, Adjacency Matrix and List 
August 7th, 2019 
Graph Traversal: BFS, Connected Components 
August 8th, 2019 
Graph Traversal: DFS, Connected Components 
August 9th, 2019 
DFS: Edge Classification, Directed Cycle Detection,Topological Sort 
August 14th, 2019 
Binary Trees: Definition, Traversal: Preorder, Inorder, Postorder 
August 16th, 2019 
Binary Search Trees: Definition, Operations: Search, Insert, Min,
Max, Successor, Delete 
August 21st, 2019 
Height Balanced BSTs: AVL Trees 
August 22nd, 2019 
AVL Trees: Insert, BST Rotations 
August 23rd, 2019 
Dynamic Programming: Binomial Coefficients 
August 28th, 2019 
Dynamic Programming: All Pair shortest Paths in Graphs 
August 29th, 2019 
Dynamic Programming: Matrix Chain Multiplication 
August 30th, 2019 
Dynamic Programming: Matrix Chain Multiplication 
Sep 4th, 2019 
Dynamic Programming: Sequence Alignment 
Sep 5th, 2019 
Greedy Algorithm: Coin Change 
Sep 6th, 2019 
Minimum Spanning Tree, Prim's Algorithm 
Sep 11th, 2019 
Kruskal's Algorithm 
Sep 12th, 2019 
Disjoint Set Data Structure 
Sep 13th, 2019 
Problem Solving 
Sep 25th, 2019 
Dijkstra's Algorithm 
Sep 26th, 2019 
Interval Scheduling: Greedy 
Sep 27th, 2019 
Interval Scheduling with deadline 
October 3rd, 2019 
Fractional Knapsack: Greedy 
October 4th, 2019 
01 Knapsack: Dynamic Programming 
October 16th, 2019 
HashTables: Chaining 
October 17th, 2019 
HashTables: Open Addressing 
October 18th, 2019 
BTrees 
October 23rd, 2019 
Heaps 
October 24th, 2019 
Heap Sort, Lower Bound on comprison based sorting 
October 25th, 2019 
Counting Sort 
October 30th, 2019 
Integer Sorting: Radix Sort, Bucket Sort 
October 31st, 2019 
Order Statistics 
November 1st, 2019 
Order Statistics 
November 6th, 2019 
String Matching: Rabin Karp 
November 7th, 2019 
String Matching: KMP Algorithm 
November 8th, 2019 
String Matching: KMP Algorithm (contd..) 
Announcements
Class Test 2 will be held on November 6th, 6:30  7:30 PM. Seating Arrangement.
Class Test 1 will be held on August 30th, 6:30  7:30 PM. Seating Arrangement.
First Algo1 class will be on July 17th, 10:00  11:00 AM
(NR424 for Section 2). First Algo Lab will be on July 18th, 2:00  5:00 PM at CIC
(PC_Lab II and PC_Lab V).
