Design and Analysis of Algorithms(DAA)
SYLLABUS:
UNIT-I Introduction
Algorithm Specification, Performance Analysis -Space complexity, Time complexity, Asymptotic Notations (Big-oh notation, Omega notation, Theta notation).
UNIT-II Divide and Conquer
General method, Binary search, Merge sort, Quick sort, Strassen’s matrix multiplication.
UNIT-III Greedy method
General method, Knapsack problem, Job sequencing with deadlines, Minimum cost spanning trees, Single source shortest paths.
UNIT-IV Dynamic Programming
The General method, All pairs shortest path problem, Optimal binary search trees, 0/1 knapsack, Reliability design, The Travelling sales person problem, Matrix-chain multiplication.
UNIT-V Backtracking
The General method, N-Queen problem, Sum of subsets, Graph coloring, Hamiltonian cycles.
Branch and Bound: The method, 0/1 knapsack problem, Travelling sales person problem.
