Instructors: Dr. Nilanjan Datta, Dr. Laltu Sardar and Dr. Ritankar Mandal
The course introduces the basics of computational complexity analysis and various algorithm design paradigms. The goal is to provide students with solid foundations to deal with a wide variety of computational problems, and to provide a thorough knowledge of the most common algorithms and data structures. After the course, a student should be able to analyze the asymptotic performance of algorithms, write rigorous correctness proofs for algorithms, and apply important algorithmic design paradigms and methods of analysis.
- Introduction: Algorithm, Instance of a problem, Efficiency of algorithm, Growth of Functions, Asymptotic notation, Worst case, Best case, Average Case time complexity, Substitution method, Recursion tree method, Masters Theorem.
- Elementary Data Structure: Array, Linked list, Stack, Queue, Heap, Binary Search Tree, AVL Tree, Hash table, Disjoint Set Data Structure.
- Searching, Sorting and Order Statistics: Linear and Binary Search, Heap Sort, Quick Sort, Sorting in linear time, Order statistics, Finding Median in linear time.
- Divide and Conquer Paradigm: Merge Sort, Counting Inversion, Closest Pair of Points.
- Greedy Algorithms: Interval Scheduling Problem and its variants, Optimal Caching Problem, Minimum Spanning tree Problem, Huffman
Code, Clustering Problem, Fractional Knapsack problem, Dijkstra Algorithm.
- Dynamic Programming: Matrix Chain Multiplication, Longest Common Subsequence, Optimal Binary Search Tree, Segmented Least Square Problem, 0/1-Knapsack Problem, Subset Sum Problem, Bellman Ford Algorithm.
- Graph algorithms: BFS, DFS, Floyd Warshall, Fold Fulkerson.
- Advanced Topics: P, NP, NPC (Circuit Satisfiability, Vertex Cover, Graph Coloring), Approximation Algorithm of some NPC Problems, Probabilistic Algorithm: Miller Rabin Primality Algorithm.
 T. H. Cormen, C. E. Leiserson and R. L. Rivest: Introduction to Algorithms, PrenticeHall of India, New Delhi, 1998.
 J. Kleinberg, E. Tardos: Algorithm Design, Pearson Education, 2006.
 A. Aho, J. Hopcroft and J. Ullman: The Design and Analysis of Computer Algorithms, A. W. L, International Student Edition, Singapore, 1998.
 E. Horowitz, S. Sahni, S. A. Freed: Fundamentals of Data Structures in C, 2008.
 S. Baase: Computer Algorithms: Introduction to Design and Analysis, 2nd ed., Addison-Wesley, California, 1988.
- Assignment 1 [PDF] (Deadline: 16/02/2023)
- Assignment 2 [PDF] (Deadline: 28/02/2023)
- Assignment 3 [PDF] (Deadline: 30/03/2023)
- Assignment 4 [PDF] (Deadline: 31/05/2023)
Classes (by Dr. Nilanjan Datta):
- Introduction to Algorithms, Insertion Sort, Correctness using Loop Invariants, Analysis of Algorithms: Best Case, Average Case, Worst Case Analysis. [Class 1]
- Asymptotic Notation, Partitioning Array corresponding to a pivot element, Quick Sort, Merge Sort. [Class 2]
- Merging two arrays in linear time, In-place Merge Sort, Stable Sorting. [Class 3]
- Data Structures: Static and Dynamic array, Linked-list; Static and Dynamic Interfaces, Max-Heap, Building a Heap. [Class 4] [Data Structure: Video Lecture by Erik Demaine]
- Heap Sort, Priority Queue, The Lower bound time complexity of comparison-based Sorting. [Class 5]
- Selection in expected O(n) running time. [Class 6]
- Linear Time Sorting: Counting Sort, Radix Sort, Bucket Sort. [Class 7]
- Randomized Algorithms and Probabilistic Analysis: Hire Assistant Problem, Avg case complexity of Randomized Quick Sort, Randomized Selection, Bucket Sort. [Class 8]
- Order Statistics: Number of comparisons required to report the minimum, 2nd minimum, simultaneous minimum and maximum element, Selection in O(n) worst case. [Class 9]
- Runway Reservation Problem, Balanced Binary Search Tree, AVL Trees – Search, Insertion, Deletion. [Class 10] [Ref: Video Lecture by Erik Demaine]
- Red Black Tree: Definition, Properties, Searching in a Red Black Tree. [Class 11]
- Insertion in Red Black Tree, Optimal Binary Search Trees, Dynamic programming to solve Optimal Binary Search Trees. [Class 12] [Ref: Lecture Note]
- Class P, NP, NP-Complete, NP-Hard [Ref: Video Lecture by Erik Demaine]
- Approximation Algorithms, Vertex Cover Problem, Traveling Salesman Problem with triangle inequality. [Class 13]
Classes (by Dr. Laltu Sardar):
- Divide and Conquer Algorithms I: Finding the Closest Pair
- Divide and Conquer Algorithms II: The maximum Sub-array Problem
Classes (by Dr. Ritankar Mandal):
- Dynamic Programming [Notes]:
- Longest Increasing Sub-sequence
- Knapsack Problem
- Shortest Reliable Paths
- All-pair Shortest Path
- Travelling Salesman Problem
- Maximum Independent Set in a Tree
- Matrix Chain Multiplication