OBJECTIVE:
To learn about Time Complexity and various algorithmic design methodologies.
Algorithms as technology – Analyzing and Designing algorithms – Asymptotic notations – Recurrences – Methods to solve recurrences – Heap Sort - Quick Sort – Sorting in linear time – Radix sort – Selection in linear time.
Divide and conquer methodology – Multiplication of large integers – Strassen's matrix multiplication – Greedy method – Prim's algorithm – Kruskal's algorithm – algorithm for Huffman codes.
Dynamic Programming – Elements – Matrix-chain multiplication –Computing a binomial coefficient – Floyd-Warshall algorithm – Optimal binary search tree – Memory functions.
Backtracking – N-Queens problem – Hamiltonian circuit problem – Subset sum problem – Branch and bound – Assignment problem – Knapsack problem – Traveling salesman problem.
NP-hard and NP-complete problems – Definitions and Properties – Reducibility – Cook’s Theorem (without proof) – Clique decision problem – Node cover problem – K-coloring problem
REFERENCES:
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, 3rd Edition, MIT Press,2009.
2. Robert Sedgewick and Philippe Flajolet, “An Introduction to the Analysis of Algorithms”, 2nd Edition, Addison-Wesley,2013
3. Jon Kleinberg and ÉvaTardos, “Algorithm Design”, Addison-Wesley,2005.
4. George T. Heineman, Gary Pollice and Stanley Selkow, “Algorithms in a Nutshell”, O'Reilly Media, 2008.
5. SanjoyDasgupta, Christos Papadimitriou and UmeshVazirani,“Algorithms”, McGraw-Hill,2006.
6. E.Horowitz, S.Sahni, and S.Rajasekaran, “Computer Algorithms”, 2nd edition, Silicon Press,2007.
Course Outcome:
Students will be able to:
1. Analyze the complexity of polynomial algorithms.
2. Apply various design strategies for solving problems
3. Distinguish NP hard and NP complete problems from other problems
