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.
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]
- Next Class: Growth of Function, Asymptotic Notation, Introduction to Data Structures.
Classes (by Dr. Laltu Sardar):
Classes (by Dr. Ritankar Mandal):