mca Syllabus

Design & Analysis of Algorithm
IT 803C
Contact: 3L
Credit: 3
Allotted Hrs: 39L

Models of computation [4L]: Random Access Machine, Relationship between Turing Machine and RAM, Time and Space Complexity.
Complexity analysis [8L]: Asymptotic notations, Recurrence for divide and conquer and its solution, Merge sort, Heap sort, Quick sort and their complexity.
Dynamic Programming [4L]: Basic method, Matrix-chain multiplication, All pair shortest paths, Singlesource shortest path, Travelling Salesman problem.
Greedy Method [5L]: Basic method, Knapsack problem, Job sequencing with deadlines, Minimum spanning tree by Prim's and Kruskal's algorithms.
Disjoint Set Manipulation [4L]: Set manipulation algorithm like UNION-FIND, Union by rank, Path compression.
Graph Traversal Algorithms [5L]: BFS and DFS, Backtracking and its use in solving Knapsack and Eight queens problem.
Matrix Manipulation Algorithms [6L]: Strassen’s Matrix-multiplication algorithm and its applications in Solution of simultaneous linear equations using LUP decomposition, Inversion of Matrix and Boolean Matrix multiplication.
Notion of NP-completeness [5L]: P class, NP-hard class, NP-complete class, Circuit Satisfiability problem.
Approximation Algorithms [4L]: Vertex cover problem, Travelling salesman problem, Set covering problem.

Books:
1. A.Aho, J.Hopcroft and J.Ullman “The Design and Analysis of algorithms”, PE.
2. T Cormen, C Leiserson and R Rivest “Introduction to Algorithms”, PHI.
3. Fundamentals of Algorithms- G.Brassard,P.Bratlay, PHI.
4. Horowitz Ellis, Sahani Sartaz, R. Sanguthevar " Fundamentals of Computer Algorithms".