Algorithms-1 - CS21003

Autumn Semester - 2019

Instructors

Prof. Animesh Mukherjee will be teaching Section-1 (Odd Roll Numbers) and I will be teaching Section-2 (Even Roll Numbers). The Timings below are same for both the sections, except that the classes for Section-1 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

  1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press, 2009.
  2. Richard Neapolitan, Foundations of Algorithms, Fifth Edition, Jones and Barlett Publishers, 2009.
  3. Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, 1989.
  4. 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, Post-order
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 0-1 Knapsack: Dynamic Programming
October 16th, 2019 HashTables: Chaining
October 17th, 2019 HashTables: Open Addressing
October 18th, 2019 B-Trees
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 Algo-1 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).