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?
Array representation: O(n), Pointer representation: O(size(c))
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(n)
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.
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.
In both min heaps and max heaps, both operations take time O(n).
In both min heaps and max heaps, both operations take time O(log n).
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).
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).
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?
27
30
37
39
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?
O(n2)
O(n2 log5n)
O(n log2n)
O(n (log2n)2)