Instructors: Prof. Rana Barua and Dr. Nilanjan Datta
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.
- Number Theoretic Algorithms: Euclidean, Extended Euclidean, CRT, Pollard Rho.
- 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.
Implement Wordle and design an algorithm to solve Wordle efficiently.
Project Presentation: 07/06/2022
Class Test on 29/03/2022 from 2:30 PM [Topic: Sorting and Order Statistics]
Mid-Semester Examination will be held on 11/04/2022 [Syllabus: Elementary Data Structures, Searching, Sorting and Order Statistics, Divide and Conquer Paradigm, Greedy Algorithms, Dynamic Programming]
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]
- Growth of Function, Asymptotic Notation, Introduction to Data Structures, Difference between Interface and Data Structure, Static Sequence Interface, Static Array. [Class 2]
- Dynamic Sequence Interface, Dynamic Array, Linked List, Doubly Linked List, A comparative study of Static Array, Linked List, and Dynamic Array with respect to the efficiency of different static and dynamic operations. [Class 3]
- Data Structures to represent Polynomials; Stack Data Structure and Its applications: Infix to Postfix Conversion, Evaluation of Postfix expression, Finding Minimum elements in the stack efficiently. [Class 4]
- Queue, Circular Queue, Priotity Queue, Heap Data Structure, Max-heap, Min-heap, Heap Sort, Implementation of Priority Queue using Heap. [Class 5]
- Fibonacci Heap, Priority Queue using Fibonacci Heap; Searching: Linear and Binary Search, Binary Search Tree, Motivation for Balanced Binary Search Tree. [Class 6]
- Balanced Binary Search Tree, AVL tree, Red-Black tree. [Class 7]
- Quick Sort, Randomized Quick Sort, Expected Running Time of Randomized Quick Sort, Comparison based Sort, Decision Tree, Lower Bound on Comparison based Sort. [Class 8]
- Sorting in Linear Time: Counting Sort, Stable Sort, Radix Sort, Bucket Sort. [Class 9]
- Medians and Order Statistics: Minimum and Maximum, Selection in expected linear time, Selection in worst case linear time. [Class 10]
- Dynamic Sets with Dictionary Operations: Direct Address Table, Hash Table, Collision Resolution by Chaining, Open Addressing: Linear and Quadratic Probing, Perfect Hashing. [Class 11]
- Dynamic Programming: Optimal Binary Search Trees, Coin Game. [Class 12]
- Graph Algorithms: Representation, BFS, DFS. [Class 13]
- Randomized Algorithms and Probabilistic Analysis. [Class 14]
Classes (by Prof. Rana Barua):
- Divide and Conquer Paradigm: Merge Sort, Counting Inversions, Closest Pair of Points. [Class 1]
- Greedy Algorithms (part I): Interval Scheduling Problem – EFT Algorithm, Minimum Spanning Tree Construction – Prim’s Algorithm. [Class 2]
- Greedy Algorithms (part II): Minimum Spanning Tree Problems: Prim’s Algorithm, Kruskal’s Algorithm, Use of union-find data structure, Clustering Problem. [Class 3]
- Greedy Algorithms (part III): Clustering Problem, Huffman Coding. [Class 4]
- Greedy Algorithms (part IV): Huffman Algorithm, Fractional Knapsack, Single-source Shortest Path, Dijkstra’s Algorithm. [Class 5]
- Dynamic Programming (part I): Longest Common Sequence, Matrix Chain Multiplication. [Class 6]
- Dynamic Programming (part II): Matrix Chain Multiplication, Subset Sum and Knapsack. [Class 7]
- Number Theoretic Algorithms (part I): Euclidean, Extended Euclidean, Chinese Remainder Theorem. [Class 8]
- Number Theoretic Algorithms (part II): Pollard’s Rho Factoring Algorithm, Miller-Rabin Algorithm for Primality Testing. [Class 9]
- Miller-Rabin Algorithm for Primality Testing (contd), Turing Machine, NP-Complete Problems [Class 10]
- NP-Complete Problems: Circuit Satisfiability, Vertex Cover, Graph Coloring. [Class 11]