Home > 2022 Scheme > Computer Science Engineering > 4th Sem > BCS401 VTU Notes: Analysis & Design of Algorithms

BCS401 VTU Notes: Analysis & Design of Algorithms

BCS401 VTU Notes: Master algorithm efficiency with our BCS401 Analysis & Design of Algorithms notes. Explore divide-and-conquer, greedy methods, and dynamic programming for the 2022 Scheme at the all-new vtubuddy.in student portal.

Analysis & Design of Algorithms

BCS401

2022 Scheme

Module 1 : INTRODUCTION

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

BRUTE FORCE APPROACHES (contd..): Exhaustive Search (Travelling Salesman probem 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

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

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

LIMITATIONS OF ALGORITHMIC POWER: Decision Trees, P, NP, and NP-Complete Problems.
COPING 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).