** LONG ANSWER IMPORTANT QUESTION OF Designing and Analysis of Algorithm form UNIT 1**

**Q1: What do you mean by algorithm? Write the characteristic of an algorithm? (ALTU 2013-14) **

**Q2: What do you understand by asymptotic notation? Describe the type of asymptotic notation in detail? (AKTU 2013-14)**

**or**

**Discuss asymptotic notations in brief ? (AKTU 2014-15)**

**Q3: The recurrence relation T(n)= 7T(n/2) + n*n describe the running time of the an algorithm A. A competing algorithm A’ has a running time of an algorithm T(n) = a T(n/4) + n*n. What is the largest integer value for a A’ is asymptotically faster than A? (AKTU 2017-18)**

**Q4: Solve the following recurrence relation ****(AKTU 2014-15)**

** T(n)=T(Square root(n)) + O(n log n) **

**Q5: What is recursion tree? Describe in detail? (AKTU 2013-14)**

**Q6: Solve the following recurrence relation ****(AKTU 2014-15)**

** T(n) = T(n/2) + T(n/4) + T(n/8) + n**

**Q7: Describe any one of the following Sorting Techniques: AKTU 2013-14**

**Selection****Sort****Insertion Sort**

**Q8: Consider the recurrence relation ****(AKTU 2013-14)**

**T(n)=3T(n/3) + c*n and T(n) = 5T(n/4) + n*n where c is constant and n is the number of inputs. Find the asymptotic bounds? **

**Q9: Solve the following by recursive tree method ****(AKTU 2017-18)**

** T(n) = n + T(n/5) + T (4n/5)**

**Q10: Write the non-deterministic algorithm for sorting? **** ****(AKTU 2016-17)**

**Q11: Explain the Quick Sort? and also analyze its complexity with suitable example? **** ****(AKTU 2016-17)**

**Q12: Discuss the best case and worst case complexity of Quick Sort algorithm in detail? **** ****(AKTU 2014-15)**

**Q13: ****Explain the concept of merge sort with example?**** **** ****(AKTU 2016-17)**

**Q14: Explain heap sort algorithm with its analysis? **** **** ****(AKTU 2014-15)**

**OR **

**What is the running time of heap sort on an array A of length n that is already sorted in increasing order? ****OR**

**Discuss the complexity of Max Heapify and Build Max Heap procedure?**

**Q15: Sort the following Array using heap sort technique { 5 , 13 , 2 , 25, 7, 17, 20, 8, 4}. Discuss its worst case and average case time complexity? **** **** ****(AKTU 2013-14)**

**Q 16: Explain HEAP SORT on the array. ****Illustrate**** the operation HEAP SORT on the array A= {6, 14, 3, 25, 2, 10, 20, 7, 6} **** **** ****(AKTU 2017-18)**

**Q17: What is the time complexity of counting sort? Illustrate the operation of count sort on array A={1,6,3,3,4,5,6,3,4,5} **** **** ****(AKTU 2014-15)**

**Q18: Write a sort note on Radix Sort, Counting Sort and Bubble Sort?**

**Q19: Write down the complexity of various sorting technique? **