Analysis and Design of Algorithms 2022 Scheme BCS401 VTU University 4th SEM Computer science and Engineerings|BCS401 notes

Scheme & Syllabus Copy of Analysis and Design of Algorithms 2022 Scheme BCS401 VTU University 4th SEM Computer science and Engineerings

Syllabus copy of Analysis and Design of Algorithms 2022 Scheme BCS401

Module 1

Introduction:What is an Algorithm?, Fundamentals of Algorithmic Problem Solving.
Fundamentals of the Analysis of Algorithm Efficiency: Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non recursive Algorithms, Mathematical Analysis of Recursive Algorithms.
Brute Force Approaches: Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching.

Module 2

Brute Force Approaches (contd..): Exhaustive Search (Travelling Salesman problem and Knapsack Problem).
Decrease and Conquer: Insertion Sort, Topological Sorting.
Divide and Conquer: Merge Sort, Quick Sort, Binary Tree Traversals, Multiplication of Large Integers and Strassen’s Matrix Multiplication.

MODULE-3

Transform and-Conquer: Balanced Search Trees, Heaps and Heapsort.
Space-Time Tradeoffs: Sorting by Counting: Comparison counting sort, Input Enhancement in String Matching: Horspool’s Algorithm.

MODULE-4

Dynamic Programming: Three basic examples, The Knapsack Problem and Memory Functions, Warshall’s and Floyd’s Algorithms.
The Greedy Method: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees and Codes.

MODULE-5

Limitations of Algorithmic Power: Decision Trees, P, NP, and NP-Complete Problems.
Copying with Limitations of Algorithmic Power: Backtracking (n-Queens problem, Subset-sum problem), Branch-and-Bound (Knapsack problem), Approximation algorithms for NP-Hard problems (Knapsack problem).