Guru Gobind Singh Indraprastha University, Kashmere Gate, Delhi-110006

SCHEME/SYLLABUS : MCA(SE)
(Second Semester)

Code No: IT 606
Paper: Algorithm Analysis and Design

Preliminaries:
Growth of functions, Summations, Recurrences: The substitution method, The iteration method, The master method, Divide and Conquer paradigm, Dynamic programming, Greedy Algorithms.

Sorting and Order Statistics:
Merge Sort, Heap sort, Quick sort, Sorting in linear time, Medians and Order statistics.

Searching and Data Structures for Disjoint Sets:
Hash Tables, Binary Search Trees, Red-Black trees, order statistic tree, disjoint-set Operations, Linked list representation of disjoint sets, Disjoint set forests.

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.

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

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

Text:

    1. T .H . Cormen, C . E . Leiserson, R .L . Rivest “Introduction to Algorithms”, PHI.

References:

    1. A .V. Aho, J . E . Hopcroft, J . D . Ulman “The Design & Analysis of Computer Algorithms”, Addison Wesley.
    2. V . Manber “Introduction to Algorithms – A Creative Approach”, Addison Wesley.
    3. Ellis Harwitz and Sartaz Sahani “Fundamentals of Computer Algorithms”, Computer Science Press.
    4. Peter Linz, “An Introduction to Formal Languages and Automata”, Narosa Publishing House.
    5. J.E.Hopcroft & J.D.Ullman, “Introduction to Automata Theory, Languages and Computation”, Addison Wesley.
    6. K.L.Mishra & N.Chandrasekaran, “Theory of Computer Science”, PHI.
    7. John C.Martin, “Introduction to Languages and Theory of Computation”, TMH.
 

Go back to MCA(SE) Syllabi Page