mca Syllabus

Design & Analysis of Algorithm
Code: CS 503
Contacts: 3L + 1T
Credits: 4
Allotted Hrs: 45L

Models of computation [4L]:
RAM,TM etc. time and space complexity

Asymptotic Notation [3L]
Big-O, omega, theta etc.; finding time complexity of well known algorithms like- heapsort, search algorithm etc.

Algorithm Design techniques [2L]
Recursion- Definition, Use, Limitations, Examples: Hanoi problem. Tail Recursion

Divide and Conquer [3L]
Basic method, use, Examples: Merge sort, Quick Sort, Binary Search

Dynamic Programming [4L]
Basic method, use, Examples: matrix-chain multiplication, All pair shortest paths, single-source shortest path, Travelling Salesman problem

Branch and Bound [2L] : Basic method, use, Examples: The 15-puzzle problem

Backtracking [3L]
Basic method, use, Examples: Eight queens problem, Graph coloring problem, Hamiltonian problem

Greedy Method [4L]
Basic method, use, Examples: Knapsack problem, Job sequencing with deadlines, minimum spanning tree(Prim's and Kruskal's algorithms)

Lower Bound Theory [2L]
Bounds on sorting and sorting techniques using partial and total orders.

Disjoint Set Manipulation [2L]
Set manipulation algorithm like UNION-FIND, union by rank, Path compression. Properties of graphs and graph traversal algorithms [3L]: BFS and DFS

Matrix manipulation algorithms [5L]
Different types of algorithms and solution of simultaneous equations, DFT & FFT algorithm; integer multiplication schemes

Notion of NP-completeness [5L]
P class, NP-hard class, NP-complete class, Circuit Satisfiability problem, Clique Decision Problem.

Approximation algorithms [3L]
Necessity of approximation scheme, performance guarantee, Polynomial time approximation schemes: 0/1 knapsack problem

Text Books:
1. A.Aho, J.Hopcroft and J.Ullman “The Design and Analysis of algorithms”
2. D.E.Knuth “The Art of Computer Programming”, Vol. I & Vol.2
3. Horowitz Ellis, Sahani Sartaz, R. Sanguthevar " Fundamentals of Computer Algorithms".
4. Goodman: Introduction to Design and Analysis Of Algorithms TMH

Reference:
1. K.Mehlhorn , “Data Structures and algorithms- Vol. I & Vol. 2 “
2. S.Baase “Computer algorithms”
3. E.Horowitz and Shani “Fundamentals of Computer algorithms”
4. E.M.Reingold, J.Nievergelt and N.Deo- “Combinational algorithms- Theory and Practice”, Prentice Hall , 1997
5. A.Borodin and I.Munro, “The computational complexity of Algebraic and Numeric problems”