Design & Analysis of Algorithm
Paper Code: IT 803C
Models of computation: Random Access Machine, Relationship between Turing Machine and RAM, Time and Space Complexity.
Complexity analysis: Asymptotic notations, Recurrence for divide and conquer and its solution, Merge sort, Heap sort, Quick sort and their complexity.
Dynamic Programming: Basic method, Matrix-chain multiplication, All pair shortest paths, Singlesource shortest path, Travelling Salesman problem.
Greedy Method: Basic method, Knapsack problem, Job sequencing with deadlines, Minimum
spanning tree by Prim’s and Kruskal’s algorithms.
Disjoint Set Manipulation: Set manipulation algorithm like UNION-FIND, Union by rank, Path
compression.
Graph Traversal Algorithms: BFS and DFS, Backtracking and its use in solving Knapsack and
Eight queens problem.
Matrix Manipulation Algorithms: 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: P class, NP-hard class, NP-complete class, Circuit Satisfiability
problem.
Approximation Algorithms: Vertex cover problem, Travelling salesman problem, Set covering
problem.
Books:
- A.Aho, J.Hopcroft and J.Ullman “The Design and Analysis of algorithms”, PE.
- T Cormen, C Leiserson and R Rivest “Introduction to Algorithms”, PHI.
- Fundamentals of Algorithms- G.Brassard,P.Bratlay, PHI.
- Horowitz Ellis, Sahani Sartaz, R. Sanguthevar ” Fundamentals of Computer Algorithms”.
