CS6402 DESIGN AND ANALYSIS OF ALGORITHMS syllabus-subject-notes-pevious-year-questions-papers-bank

OBJECTIVES:

The student should be made to:

Learn the algorithm analysis techniques.

Become familiar with the different algorithm design techniques.

Understand the limitations of Algorithm power.

UNIT I INTRODUCTION 9

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 9

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 9

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 9

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 9

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.

OUTCOMES:

At the end of the course, the student should be able to:

Design algorithms for various computing problems.

Analyze the time and space complexity of algorithms.

Critically analyze the different algorithm design techniques for a given problem.

Modify existing algorithms to improve efficiency.

TEXT BOOK:

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson

Education, 2012.

REFERENCES:

1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to

Algorithms”, Third Edition, PHI Learning Private Limited, 2012.

2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson

Education, Reprint 2006.

3. Donald E. Knuth, “The Art of Computer Programming”, Volumes 1& 3 Pearson Education, 2009.

Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2008.

OBJECTIVES:

The student should be made to:

Learn the algorithm analysis techniques.

Become familiar with the different algorithm design techniques.

Understand the limitations of Algorithm power.

UNIT I INTRODUCTION 9

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 9

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 9

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 9

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 9

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.

OUTCOMES:

At the end of the course, the student should be able to:

Design algorithms for various computing problems.

Analyze the time and space complexity of algorithms.

Critically analyze the different algorithm design techniques for a given problem.

Modify existing algorithms to improve efficiency.

TEXT BOOK:

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson

Education, 2012.

REFERENCES:

1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to

Algorithms”, Third Edition, PHI Learning Private Limited, 2012.

2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson

Education, Reprint 2006.

3. Donald E. Knuth, “The Art of Computer Programming”, Volumes 1& 3 Pearson Education, 2009.

Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2008.

## No comments:

## Post a Comment