Job Saarnee

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

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?

Shopping Cart