CS2251 DESIGN AND ANALYSIS OF ALGORITHMS
UNIT I
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
Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.
UNIT III
Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem.
UNIT IV
Backtracking: General Method – 8 Queens Problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.
UNIT V
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.
TEXT BOOKS:
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.