Design and Analysis of Algorithms PCCST502 Semester 5 KTU CS 2024 Scheme - Dr Binu V P

About Me - Dr Binu V P

Syllabus and Scheme

Model Question Paper Design and Analysis of Algorithms PCCST502 KTU 2024 Scheme

Module - I

• Introduction to Algorithms
• Criteria for Analyzing Algorithms - Time and Space Complexity
• Performance Analysis - Time and Space Complexity
• Asymptotic Analysis , Asymptotic Notations and their properties
• Comparing Growth Rates using Limits
• Standard Functions and notations
• Properties of Asymptotic Notations and common conjuctures
• Analyzing Algorithms - Insertion Sort ( Example )
• Divide and Conquer Strategy using Merge Sort
• Divide and Conquer - Recurrences
• Analysis of Recursive Algorithms
• Iteration Method(Expansion Method)
• Substitution Method
• Example Problems - Substitution Method
• Recursion Tree Method
• Example Problems - Recursion Tree Method
• Master Method
• Example Problems-Master Method
• Akra-Bazzi Method
• Recurrences where the Master Theorem cannot be Applied
• Balanced Search Trees - AVL Trees

Module - II

Disjoint Sets

• Disjoint Sets (Union-Find Data Structure)
• Linked List Representation of Disjoint Sets
• Disjoint Set Forest
• Application of Disjoint-Set Data Structure: Connected Components

Graphs

• Introduction to Graph and Graph Algorithms
• Types of Graphs
• Graph Representations 
• Significance of Adjacency List and Adjacency Matrix Representation in Algorithm Analysis

BFS

• Breadth-First Search (BFS)
• Complexity Analysis of BFS
• How BFS creates shortest path
• Breadth-First Tree in BFS

DFS

• Depth First Search ( DFS)
• Complexity Analysis of DFS
• Classification of Edges in DFS
• Topological Sorting Using DFS
• Strongly Connected Components using DFS
• Applications of Strongly Connected Components

Divide and Conquer Strategy using Merge Sort

Strassen's Matrix Multiplication

Module - III

• Greedy Algorithm-Fractional Knapsack Problem
• Introduction to Minimum Cost Spanning Tree
• Kruskal's Algorithm
• Prim's Algorithm
• Single-source shortest-path problem - Dijkstra's Algorithm

• Introduction to Dynamic Programming
• Matrix Chain Multiplication using Dynamic Programming
• Floyd-Warshall Algorithm- All pairs shortest paths

• Backtracking  N-queens problem

Module - IV

• Branch and Bound - Travelling Salesman Problem (TSP)

• Tractable and Intractable Problems
• Complexity Classes: P, NP, NP-Hard and NP-Complete
• NPC vs NPH

• Clique Problem
• Proof of NP Completeness - Clique Problem
• Vertex cover problem

• Introduction to Approximation Algorithms
• Bin Packing Problem and First-Fit Approximation Algorithm
• Randomized Algorithms - Monte Carlo and  Las Vegas algorithms
• Randomized Quicksort