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

`Course Objective:`

`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:`

`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:`

`References:`

[1] T. H. Cormen, C. E. Leiserson and R. L. Rivest: Introduction to Algorithms, PrenticeHall of India, New Delhi, 1998.

[2] J. Kleinberg, E. Tardos: Algorithm Design, Pearson Education, 2006.

[3] A. Aho, J. Hopcroft and J. Ullman: The Design and Analysis of Computer Algorithms, A. W. L, International Student Edition, Singapore, 1998.

[4] E. Horowitz, S. Sahni, S. A. Freed: Fundamentals of Data Structures in C, 2008.

[5] S. Baase: Computer Algorithms: Introduction to Design and Analysis, 2nd ed., Addison-Wesley, California, 1988.

**Assignments:**

**Assignments:**

- 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):**

**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):**

**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):`

`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