1.In Quicksort of the following numbers, if the pivot is chosen as the first element,what will be the order of the numbers after the use of partition function? Assume we are sorting in increasing order.
11 15 9 13 17 7 5 12 6 18

 Ans: C) 6 9 7 5 11 15 13 12 17 18

2.What is the max heap property?

Ans: C) Value of parent > Value of children

3.While sorting the following numbers using Quicksort, the last number is chosen as pivot, what will be the permutation of the numbers after the partition function has been applied?
70 48 76 58 43 47 78 53

Ans: A) 48 43 47 53 70 76 78 58

4.Build the max heap from the following numbers and find the correct order after max heap has been built. Start from node ⌊n2⌋, use the siftdown method
6 2 8 3 14 11 13 9 15

Ans: B) 15 14 13 9 6 11 8 2 3

5. What is the best case time complexity of Quicksort?

Ans: A) Θ(n.log n).

6.What is the height of a binary heap?

Ans: C) O( log n)

7.What is the recurrence relation of the best case in Quicksort?

Ans: B) T(n)=2T(n/2)+ Θ(n)

8.Max heap is built using the following numbers, what will be the new position of 12 and 6,respectively. Assume that the root has position number 1. Start from node⌊n2⌋ , use the siftdown method
12 1 4 8 6 13 9 3

Ans: A) 3,5

9.Which of the following algorithms is better when dealing with reverse sorted numbers?

C) Insertion Sort

Ans: B) Heapsort

10. ______________ element of an input array is used as pivot in Randomized Quick sort

Ans: D) A randomly selected

 

Categories: NPTEL solution

11 Comments

Rishab · August 14, 2017 at 3:27 PM

Can you explain answer for third one .

    yashrs · August 15, 2017 at 4:58 AM

    As 53(last element) is the pivot element, after the partition all the numbers left to 53 will be less than that, and all the numbers on right side of 53 will be greater than that. Hence, the answer is ((48 43 47)) 53 ((70 76 78 58))

Rishab · August 20, 2017 at 2:36 PM

please upload the answers for 4th week

Rishab · August 30, 2017 at 12:04 PM

Please assignment 5 and 6 solution. Today is the last date

    Smit Parmar · August 31, 2017 at 3:47 PM

    just give us two days, we provide you soon

Rishab · September 3, 2017 at 9:25 AM

please provide the answers for assignment 4 and 5

Rishab · September 3, 2017 at 9:25 AM

sorry 5 and 6

Leave a Reply

Your email address will not be published. Required fields are marked *