Instructors: Dr. Nilanjan Datta, Dr. Laltu Sardar and Dr. Ritankar Mandal

##### Course Objective:

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.

##### Syllabus:
• 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.

##### References:

 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.