 COURSE SUMMARY
Course Title:
Design and Analysis of Algorithms
Course Code:
15CSE211
Year Taught:
2015
2016
2017
2018
Semester:
4
Type:
Subject Core
Degree:
School:
School of Engineering
Campus:
Bengaluru
Chennai
Coimbatore
Amritapuri

'Design and Analysis of Algorithms' is a course offered in the fourth semester of B. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.

#### SYLLABUS

Unit 1

Introduction - Algorithms vs programs. Flow charts and pseudo code, Rate of growth of functions. Asymptotic notation: motivation and types of notations. Recurrence relations and methods to solve them: Recursion tree, substitution, Master Method, Sorting: Bubble – Insertion – Selection – Bucket – Heap, Comparison of sorting algorithms, Divide and Conquer: Quick sort – Merge sort – Binary search – Long integer multiplication – Maximum sub array sum.

Unit 2

Greedy Algorithm - Introduction to the method, Fractional Knapsack problem, Task Scheduling Problem, Dynamic Programming: Introduction to the method, Fibonacci numbers, 0-1 Knapsack problem, Matrix chain multiplication problem. Backtracking, Branch and Bound 0-1 Knapsack, N- Queen problem.

Unit 3

Graph Algorithms - Graph Traversal: Applications of BFS: distance, connectivity and connected components and cycles in undirected graphs. Applications of DFS: Topological sort, cycles in directed graphs, Biconnected Components and Strong Connectivity. Path algorithms: Shortest path algorithms (along with analysis) SSSP: Bellman Ford. APSP: Floyd Warshall’s. Minimum Spanning Tree (with analysis and applications). Introduction to NP class: Definitions P, NP, NP complete, NP hard, Examples of P and NP.

#### TEXTBOOK

• Goodrich M. T. and Tamassia R., “Algorithm Design Foundations - Analysis and Internet Examples”, John Wiley and Sons, 2007.

#### REFERENCES

• Cormen T. H., Leiserson C. E., Rivest R. L. and Stein C., “Introduction to Algorithms”, Prentice Hall of India Private Limited, Third Edition, 2009.
• Dasgupta S., Papadimitriou C. and Vazirani U., “Algorithms”, Tata McGraw-Hill, 2009.