**Instructors:** Prof. Rana Barua and Dr. Nilanjan Datta

`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.**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.

`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 (
**Deadline:****06/03/2022**) - Assignment 2 (
**Deadline:****06/03/2022**) - Assignments 3 (
**Deadline: 03/04/2022**) - Assignments 4 (
**Deadline:****03/04/2022**) - Assignments 5 (
**Deadline:****23/05/2022**)

`Project: `

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

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

**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]

`Notes (by Prof. Rana Barua):`

`Notes (by Prof. Rana Barua):`