Categories

CS6402 Syllabus Design and Analysis of Algorithms

UNIT I INTRODUCTION CS6402 Syllabus

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.

UNIT II BRUTE FORCE AND DIVIDE-AND-CONQUER Design and Analysis of Algorithms Syllabus

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.

UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE CS6402 Syllabus

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.

UNIT IV ITERATIVE IMPROVEMENT Design and Analysis of Algorithms Syllabus

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

UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER CS6402 Syllabus

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.

 Subject Name Design and Analysis of Algorithms Subject code CS6402 Regulation 2013