# KTU Algorithm Analysis And Design Notes | 2019 Scheme

KTU  Algorithm Analysis And  Design AAD CST306 is an S6 CSE 2019 scheme course. Students will learn how to create computer algorithms as well as how to analyze them in this course. Algorithm design and analysis are essential in the daily work of a skilled programmer because they provide the theoretical backbone of computer science. The purpose of this course is to give students a good foundation in the creation and analysis of the key algorithms classes. Students will be able to create their own versions of a specific computational assignment and compare and contrast their results at the end of the course.

Classify a problem as computationally tractable or intractable, and discuss strategies to address intractability. Identify the suitable design strategy to solve a given problem. The Notes for Algorithm Analysis And  Design (AAD) are easily available on our website (www.keralanotes.com).

 Board KTU Scheme 2019 New Scheme Year Third Year Semester S6 Subject CST 306 | Algorithm Analysis And  Design Credit 4 Category KTU S6 Computer Science

### Module 1 - Syllabus

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 - Syllabus

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 - Syllabus

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 - Syllabus

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 - Syllabus

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.

### KTU S6 CSE Related Links

We hope the given KTU S6 Computer Science (CSE) Latest 2019 Scheme Syllabus, Notes, Study Materials, Previous Year Questions, and Other Materials will help you.

If you have any queries regarding the KTU S6 Computer Science (CSE) Study Materials, drop a comment below and we will get back to you at the earliest.

Keralanotes.com      Keralanotes.com      Keralanotes.com      Keralanotes.com      Keralanotes.com