NPTEL Design and Analysis of Algorithms Week 5 Assignment Answers 2024
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 the most accurate upper bound for the cost of adding Reset(c) to the array and pointer implementations of union-find discussed in the lecture?
- Array representation: O(size(c)), Pointer representation: O(size(c))
- Array representation: O(size(c)), Pointer representation: O(n)
- Array representation: O(n), Pointer representation: O(size(c))
- Array representation: O(n), Pointer representation: O(n)
Answer :- For Answers Click Here
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.
- Arguing that every d/2 side square in the d-band around the separator can have at most one point.
- Constructing SY from QY and RY in time O(n) in the combine step.
- Constructing QX and RX from PX in time O(n) in the divide step
- Constructing QY and RY from PY in time O(n) in the divide step.
Answer :- For Answers Click Here
3. Suppose we want to delete an arbitrary element from a max heap. (Assume we have auxiliary arrays NodeToHeap[] and HeapToNode[] required for the update() operation.)
Consider the following strategies.
- Strategy 1: Remove the element from the array, compress the array and reheapify.
- Strategy 2: Update the value of this node to the current maximum value in the heap + 1 and readjust the heap, then delete_max.
- Strategy 1 takes time O(n) and Strategy 2 takes time O(log n)
- Strategy 1 takes time O(log n) and Strategy 2 takes time O(n)
- Strategy 1 takes time O(n) and Strategy 2 takes time O(n log n)
- Strategy 1 takes time O(n log n) and Strategy 2 takes time O(n)
Answer :- For Answers Click Here
4. Consider the max-heap [90, 77, 89, 51, 38, 64, 89, 17, 33] built by repeatedly inserting values into an empty heap. Which of the following could not have been the last element inserted into this heap?
- 77
- 51
- 38
- 33
Answer :-
5. Suppose we implement merge sort with a 7-way split: divide the array into 7 equal parts, sort each part and do a 7 way merge. What would the worst-case complexity of this version be?
- O(n2)
- O(n2 log7n)
- O(n (log2n)2)
- O(n log2n)
Answer :- For Answers Click Here
