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?