UNIT-1 Introduction : Role of Algorithms in computing, Order Notation, Recuπences, Probabilistic Analysis and Randomized Algorithms. Sorting and Order Statistics: Heap sort, Quick sort and Sorting in Linear Time. Advanced Design and Analysis Techniques : Dynamic Programming- Matrix chain Multiplication, Longest common Subsequence and optimal binary Search trees. (Chapters - 1, 2) UNIT-11 Greedy Algorithms - Huffman Codes, Activity Selection Problem. Amortized Analysis. Graph Algorithms : Topological Sorting, Minimum Spanning trees, Single Source Shortest Paths, Maximum Flow algorithms. (Chapters - 3, 4) UNIT-111 Sorting Networks: Compaήson Networks, Zero-one principle, bitonic Sorting Networks, Merging Network, Sorting Network. Matrix Operations - Strassen's Matrix Multiplication, inverting matrices, Solving system oflinear Equations. (Chapters - 5, 6) UNIT-IV String Matching : Naive String Matching, Rabin-Karp algorithm, matching with finite Automata, ΚnuthMoπis - Pratt algorithm. (Chapter - 7) UNIT-V NP-Completeness and Approximation Algorithms : Polynomial time, polynomial time verification, NP-Completeness and reducibility, NP-Complete problems. Approximation Algorithms- Vertex cover Problem, Travelling Sales person problem. (Chapter - 8)
