Paper Code: ETCS 204	L          T          C
Paper: Algorithm Analysis & Design	3           1           4

UNIT - I

Preliminaries:

Review of growth of functions, Recurrences: The substitution method, The iteration method, The master method, Data Structures for Disjoint Sets.

Divide and Conquer Approach:

Merge Sort, Quick sort, Medians and Order statistics, Strassen's algorithm for Matrix Multiplications.

UNIT - II

Dynamic Programming:

Elements of Dynamic Programming, Matrix Chain Multiplication, Longest common subsequence and optimal binary search trees problems.

Greedy Algorithms:

Elements of Greedy strategy, An activity selection problem, Huffman Codes, A task scheduling problem.

UNIT - III

Graph Algorithms:

Representation of Graphs, Breadth First Search, Depth First Search, Topological Sort, Strongly Connected Components, Algorithm for Kruskal's and Prim's for finding Minimum cost Spanning Trees, Dijkstra's and Bellman Fort Algorithm for finding Single source shortest paths. All pair shortest paths and matrix multiplication, Floyd – Warshall algorithm for all pair shortest paths.

UNIT - IV

String matching:

The naïve String Matching algorithm, The Rabin-Karp Algorithm, String Matching with finite automata, The Knuth-Morris Pratt algorithm.

NP-Complete Problem:

Polynomial-time verification, NP-Completeness and Reducibility, NP-Completeness Proof, NP-Complete problems.

TEXT BOOKS:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, "Introduction to Algorithms", 2nd Ed., PHI, 2004.

REFERENCE BOOKS:

1. A. V. Aho, J. E. Hopcroft, J. D. Ullman, "The Design and Analysis of Computer Algorithms", Addition Wesley, 1998.
2. Ellis Horowitz and Sartaz Sahani, “Computer Algorithms”, Galgotia Publications, 1999.
3. D. E. Knuth, “The Art of Computer Programming”, 2nd Ed., Addison Wesley, 1998