|
B.Tech. IT 5th Sem Subject: Analysis And Design of Alogoritham
UNIT - 1 PERFORMANCE ANALYSIS Space and Time Complexity, Asymptotic Notations, Divide and Conquer, Finding Maxima and Minima, Binary search, Merge Sort, Quick Sort, selection sort.
UNIT - 2 GREEDY METHOD Knapsack problem, Job Sequencing, Optimal Merge Patters, Minimum Spanning trees, Dynamic Programming, All pairs shortest path, optimal binary search tree, o/1 knapsack problem, traveling sales man problem, flow shop scheduling.
UNIT - 3 SEARCH TECHNIQUES Techniques for binary trees, techniques for graphs – DES and BFS, connected components and spanning tree, Bi-connected components and DFS, Backtracking, The 8-queen problem, graph coloring, Hamiltonian cycles.
UNIT - 4 BRANCH AND BOUND O/1 knapsack problem, traveling sales person problem, efficiency consideration, Algebraic Problems, Lower Bound theory.
UNIT - 5 NP HARD AND NP COMPLETE PROBLEM Basic concepts, problem classes, P, NP, NP hard, NP complete problem, deterministic and non deterministic polynomial time algorithm.
|
