101401 DESIGN AND ANALYSIS OF ALGORITHMS B.E Computer Science And Engineering SYLLABUS 4th Semester Anna University of Technology

101401                  DESIGN AND ANALYSIS OF ALGORITHMS                        3 1 0 4

UNIT I                                                                                                                                 9

Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.

UNIT II                                                                                                                                 9

Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.

UNIT III                                                                                                                                9

Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .

UNIT IV                                                                                                                                9

Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.

UNIT V                                                                                                                                 9

Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.

TUTORIAL     = 15                                         Total = 60

TEXT BOOK:

1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II  to V)
2. K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)

REFERENCES:

1.    T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms",      Second Edition, Prentice Hall of India Pvt. Ltd, 2003.

2.    Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms",  Pearson Education, 1999.