DESIGN AND ANALYSIS OF ALGORITHMS
Subject Code: 10CS43
I.A. Marks : 25
Hours/Week : 04
Exam Hours: 03
Total Hours : 52
Exam Marks: 100
PART – A
UNIT – 1 7 Hours
INTRODUCTION: Notion of Algorithm, Review of Asymptotic Notations, Mathematical Analysis of Non-Recursive and Recursive Algorithms Brute Force Approaches: Introduction, Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching.
UNIT - 2 6 Hours
DIVIDE AND CONQUER: Divide and Conquer: General Method, Defective Chess Board, Binary Search, Merge Sort, Quick Sort and its performance.
UNIT - 3 7 Hours
THE GREEDY METHOD: The General Method, Knapsack Problem, Job Sequencing with Deadlines, Minimum-Cost Spanning Trees: Prim’s Algorithm, Kruskal’s Algorithm; Single Source Shortest Paths.
UNIT - 4 6 Hours
DYNAMIC PROGRAMMING: The General Method, Warshall’s Algorithm, Floyd’s Algorithm for the All-Pairs Shortest Paths Problem, Single-Source Shortest Paths: General Weights, 0/1 Knapsack, The Traveling Salesperson problem.
PART – B
UNIT - 5 7 Hours
22 DECREASE-AND-CONQUER APPROACHES, SPACE-TIME TRADEOFFS: Decrease-and-Conquer Approaches: Introduction, Insertion Sort, Depth First Search and Breadth First Search, Topological Sorting Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching.
UNIT – 6 7 Hours
LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH THEM: Lower-Bound Arguments, Decision Trees, P, NP, and NP-Complete Problems, Challenges of Numerical Algorithms.
UNIT - 7 6 Hours
COPING WITH LIMITATIONS OF ALGORITHMIC POWER: Backtracking: n - Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem. Branch-and-Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem. Approximation Algorithms for NP-Hard Problems – Traveling Salesperson Problem, Knapsack Problem
UNIT – 8 6 Hours
PRAM ALGORITHMS: Introduction, Computational Model, Parallel Algorithms for Prefix Computation, List Ranking, and Graph Problems,