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.