DAA WEEK -2 ASSIGNMENT

DESIGN AND ANALYSIS OF ALGORITHMS

18CS42

SUBMISSION DATE:07-04-2020

ASSIGNMENT -1
Q.No.	Questions	Marks
1.	Trace the Merge Sort algorithm for the data set 1.      8,4,1,6,7,2,3,9 2.      M,E,R,G,E,S,O,R,T Show the Values  of variables at each step.draw the tree of recursive calls made	8
2.	Apply Quick sort  to sort to the following list; Draw the tree of recursive calls made. 1.      ‘QUESTION’ in alphabetical order. 2.      65,70,75,80,85,60,55,50,45	8
3.	Explain the complexity of following algorithm ; Quick sort	4
ASSIGNMENT-II
1.	Solve the recuurence relation  for the following choices of a,b, and f(n) where c is a constant.. Use the substitution method and master’s theorem to solve the following problem. (a)    a=28 ,b=3 and f(n)=cn3 (b)   a=5 , b=4 and f(n)=cn2	8
2.	Solve the recuurence relation ; Use the substitution method and master’s theorem to solve the following problem. (c)    T(n)=25T(n/5)+18n2   for n>=2   where n is power of 5 assume T(1) as a constant.	6
3.	Apply Strassen’s  multiplication to multiply following matrices:               X	4
4.	Consider the graph: a.       Apply Dfs traversal method to get topological order b.      Apply source removal method to get  topological order:	7