Syllabus

Module-1 (Introduction to Algorithm Analysis) Characteristics of Algorithms, Criteria for Analysing Algorithms, Time and Space Complexity – Best, Worst and Average Case Complexities, Asymptotic Notations – Big-Oh (O), Big- Omega (Ω), Big-Theta (Θ), Little-oh (o) and Little- Omega (ω) and their properties. Classifying functions by their asymptotic growth rate, Time and Space Complexity Calculation of simple algorithms. Analysis of Recursive Algorithms: Recurrence Equations, Solving Recurrence Equations – Iteration Method, Recursion Tree Method, Substitution method and Master’s Theorem (Proof not required).

Module–2 (Advanced Data Structures and Graph Algorithms) Self Balancing Tree – AVL Trees (Insertion and deletion operations with all rotations in detail, algorithms not expected); Disjoint Sets- Disjoint set operations, Union and find algorithms. DFS and BFS traversals – Analysis, Strongly Connected Components of a Directed graph, Topological Sorting.

Module–3 (Divide & Conquer and Greedy Strategy) The Control Abstraction of Divide and Conquer- 2-way Merge sort, Strassen’s Algorithm for Matrix Multiplication-Analysis. The Control Abstraction of Greedy Strategy- Fractional Knapsack Problem, Minimum Cost Spanning Tree Computation- Kruskal’s Algorithms – Analysis, Single Source Shortest Path Algorithm – Dijkstra’s Algorithm-Analysis.

Module-4 (Dynamic Programming, Back Tracking and Branch & Bound)) The Control Abstraction- The Optimality Principle- Matrix Chain Multiplication-Analysis, All Pairs Shortest Path Algorithm – Floyd-Warshall Algorithm-Analysis. The Control Abstraction of Back Tracking – The N Queen’s Problem. Branch and Bound Algorithm for Travelling Salesman Problem.

Module-5 (Introduction to Complexity Theory) Tractable and Intractable Problems, Complexity Classes – P, NP, NP- Hard and NP-Complete Classes- NP Completeness proof of Clique Problem and Vertex Cover Problem- Approximation algorithms- Bin Packing, Graph Coloring. Randomized Algorithms (Definitions of Monte Carlo and Las Vegas algorithms), Randomized version of Quick Sort algorithm with analysis.

Self Balancing Trees – Properties of AVL Trees

Self Balancing Trees – Rotations of AVL Trees

AVL Trees Insertion and Illustration

AVL Trees Deletion and Illustration

Disjoint set operations.

Graph Algorithms: BFS traversal, Analysis.

Graph Algorithms: DFS traversal, Analysis.

Strongly connected components of a Directed graph.

Topological Sorting.

Divide and Conquer: The Control Abstraction.

2-way Merge Sort, Analysis.

Strassen’s Algorithm for Matrix Multiplication, Analysis

Greedy Strategy: The Control Abstraction.

Fractional Knapsack Problem

Minimum Cost Spanning Tree Computation- Kruskal’s Algorithm, Analysis.

Single Source Shortest Path Algorithm – Dijkstra’s Algorithm

Illustration of Dijkstra’s Algorithm-Analysis.

Dynamic Programming-The Control Abstraction

The Optimality Principle

Matrix Chain Multiplication-Analysis

Floyd-Warshall Algorithm-Analysis

The Control Abstraction of Back Tracking

The Control Abstraction of Back Tracking – The N Queen’s Problem

Branch and Bound Algorithm for Travelling Salesman Problem.

Tractable and Intractable Problems

Complexity Classes – P, NP

NP- Hard and NP- Complete Classes

NP Completeness proof of Clique Problem

NP Completeness proof of Vertex Cover Problem

Approximation algorithms- Bin Packing

Graph Coloring.

Randomized Algorithms

Randomized version of Quick Sort algorithm with analysis.