ItsAcademics

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)=cn 3 (b)    a=5 , b=4 and f

DESIGN AND ANALYSIS OF ALGORITHMS 18CS42 SUBMISSION DATE:01-04-2020 ASSIGNMENT -1 Q.No. Questions Marks 1. What is an Algorithm? Brief the Properties.                                                5 1.                      List the steps to write an algorithm? 5 2.                      Write an algorithm   using the specification for computing gcd(m,n) using Euclid’s algorithm. and find the space complexity for the   algorithm. [Note: The  Euclid's algorithm  (or  Euclidean Algorithm ) is a method for efficiently finding the  greatest common divisor  ( GCD) of two numbers . The  GCD of two integers X and Y is the largest  number  that divides both of X and Y (without leaving a remainder).] 5 3.          Define   time complexity?Determine the no. of steps needed by the algorithm using   frequency