Design and analysis of algorithms Nptel Week 5 Quiz Answers
Are you looking for Nptel Design and analysis of algorithms Week 5 Quiz Answers? Get Nptel assignment answers of this course
Table of Contents
Design and analysis of algorithms Week 5 Quiz Answers (July-Dec 2025)
Question 1. Suppose we want to extend the union-find data structure to support the operation Reset(c), which takes as input the name of a component c and then breaks up c into singleton components, like MakeUnionFind(). For instance if c = 3 and c currently consists of {1,3,7}, then Reset(c) will produce three components called 1, 3 and 7 consisting of {1}, {3} and {7}, respectively. Which of the following is correct about the cost of adding Reset(c) to the array and pointer implementations of union-find discussed in the lecture?
a) Array representation: O(n), Pointer representation: O(size(c))
b) Array representation: O(size(c)), Pointer representation: O(size(c))
c) Array representation: O(size(c)), Pointer representation: O(n)
d) Array representation: O(n), Pointer representation: O(n)
Question 2. In the algorithm presented for the closest pair of points problem, we have assumed that no two points have the same x or y coordinate. Which of the following steps would become more complicated to justify without this assumption.
a) Arguing that every d/2 side square in the d-band around the separator can have at most one point.
b) Constructing SY from QY and RY in time O(n) in the combine step.
c) Constructing QX and RX from PX in time O(n) in the divide step.
d) Constructing QY and RY from PY in time O(n) in the divide step.
Question 3. Suppose we want to support the operations predecessor and successor in a heap. Given a value v in the heap, pred(v) tells us the next smaller value currently in the heap and succ(v) tells us the next larger value currently in the heap.
a) In both min heaps and max heaps, both operations take time O(n).
b) In both min heaps and max heaps, both operations take time O(log n).
c) In a min heap, pred(v) takes time O(log n) and succ(v) takes O(n) whereas in a max heap pred(v) takes time O(n) and succ(v) takes O(log n).
d) In a min heap, pred(v) takes time O(n) and succ(v) takes O(log n) whereas in a max heap pred(v) takes time O(log n) and succ(v) takes O(n).
Question 4. Consider the min-heap [12, 27, 48, 30, 37, 79, 54, 43, 39] built by repeatedly inserting values into an empty heap. Which of the following could not have been the last element inserted into this heap?
a) 27
b) 30
c) 37
d) 39
Question 5. Suppose we implement merge sort with a five-way split: divide the array into 5 equal parts, sort each part and do a 5 way merge. What would the worst-case complexity of this version be?
a) O(n²)
b) O(n² log₅n)
c) O(n log₂n)
d) O(n (log₂n)²)
Design and analysis of algorithms Week 5 Quiz Answers (Jan-Apr 2025)
Course link: Click here
- What is the best upper bound you can estimate for the total time taken across all the updates made by the function?
A. O(N²)
B. O(N² log N)
C. O(N³)
D. O(N³ log N)
Answer: View Answer
- What would be the complexity of the operation reassign(j, k) in the Union-Find data structure?
A. O(1) for both the array representation and the pointer representation.
B. O(1) for the array representation, but not O(1) for the pointer representation.
C. O(1) for the pointer representation, but not O(1) for the array representation.
D. Not O(1) for either the array representation or the pointer representation.
Answer: View Answer
- What is the most accurate description of the worst-case complexity of find_max in a min-heap?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: View Answer
- What was the structure of the max-heap before inserting 57 if the resulting heap is [82,57,27,42,25,18,25,27,32]?
A. [82,42,32,27,25,18,25,27]
B. [82,27,42,32,25,18,25,27]
C. [82,42,27,25,32,18,25,27]
D. [82,42,27,32,25,18,25,27]
Answer: View Answer
- Consider an alternative to binary search called ternary search that divides the input array into three equal parts and recursively searches one of these three segments. What can we say about the asymptotic worst-case complexity of ternary search versus binary search?
A. The complexity of ternary search is the same as that of binary search.
B. The complexity of binary search is strictly better than that of ternary search.
C. The complexity of ternary search is strictly better than that of binary search.
D. The relative complexity of ternary and binary search depends on the distribution of values across the array.
Answer: View Answer
For answers or latest updates join our telegram channel: Click here to join
These are Design and analysis of algorithms Week 5 Quiz Answers
For answers to additional Nptel courses, please refer to this link: NPTEL Assignment