Design and Analysis of Algorithms

CS6402
CSE IT IT

Unit 1

INTRODUCTION

Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types – Fundamentals of the Analysis of Algorithm Efficiency – Analysis Framework – Asymptotic Notations and its properties – Mathematical analysis for Recursive and Non-recursive algorithms. I

Part A (2m) Part B (16m)

Unit 2

BRUTE FORCE AND DIVIDE-AND-CONQUER

Brute Force - Closest-Pair and Convex-Hull Problems-Exhaustive Search - Traveling Salesman Problem - Knapsack Problem - Assignment problem. Divide and conquer methodology – Merge sort – Quick sort – Binary search – Multiplication of Large Integers – Strassen’s Matrix Multiplication-Closest-Pair and Convex-Hull Problems. I

Part A (2m) Part B (16m)

Unit 3

DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

Computing a Binomial Coefficient – Warshall’s and Floyd’ algorithm – Optimal Binary Search Trees – Knapsack Problem and Memory functions. Greedy Technique– Prim’s algorithm- Kruskal's Algorithm- Dijkstra's Algorithm-Huffman Trees. 45

Part A (2m) Part B (16m)

Unit 4

ITERATIVE IMPROVEMENT

The Simplex Method-The Maximum-Flow Problem – Maximm Matching in Bipartite Graphs- The Stable marriage Problem.

Part A (2m) Part B (16m)

Unit 5

COPING WITH THE LIMITATIONS OF ALGORITHM POWER

Limitations of Algorithm Power-Lower-Bound Arguments-Decision Trees-P, NP and NP-Complete Problems--Coping with the Limitations - Backtracking – n-Queens problem – Hamiltonian Circuit Problem – Subset Sum Problem-Branch and Bound – Assignment problem – Knapsack Problem – Traveling Salesman Problem- Approximation Algorithms for NP – Hard Problems – Traveling Salesman problem – Knapsack problem.

Part A (2m) Part B (16m)
Related Notes
Generic placeholder image
Material test
notes
121 Pages, 5.2 MB

Generic placeholder image
Kinematics of donket
2m
15 Pages, 0.3 MB