Data Structures and Algorithms Union-Find Question 1 Give the id[] array that re

Question

Data Structures and Algorithms

Union-Find

Question 1
Give the id[] array that results from the following sequence of 6 union
operations on a set of 10 items using the quick-find algorithm.

    3-6 4-5 9-4 7-0 9-0 3-7

Recall: our quick-find convention for the union operation p-q is to change id[p](and perhaps some other entries) but not id[q].

Answer for Question 1

The correct answer is: 0 1 2 0 0 0 0 0 8 0

Here is the id[] array after each union operation:

         0 1 2 3 4 5 6 7 8 9

3-6: 0 1 2 6 4 5 6 7 8 9

4-5: 0 1 2 6 5 5 6 7 8 9

9-4: 0 1 2 6 5 5 6 7 8 5

7-0: 0 1 2 6 5 5 6 0 8 5

9-0: 0 1 2 6 0 0 6 0 8 0

3-7: 0 1 2 0 0 0 0 0 8 0

===================================================================

Question 2
Give the id[] array that results from the following sequence of 9 union
operations on a set of 10 items using the weighted quick-union algorithm from lecture.

    2-7 9-0 4-6 5-8 3-5 2-5 4-0 5-9 9-1

Recall: when joining two trees of equal size, our weighted quick union convention is to make the root of the second tree point to the root of the first tree. Also, our weighted quick union algorithm uses union by size (number of nodes), not union by height.

The correct answer is: 9 5 5 5 5 5 4 2 5 4

Here is the id[] array after each union operation:

      0 1 2 3 4 5 6 7 8 9

2-7: 0 1 2 3 4 5 6 2 8 9

9-0: 9 1 2 3 4 5 6 2 8 9

4-6: 9 1 2 3 4 5 4 2 8 9

5-8: 9 1 2 3 4 5 4 2 5 9

3-5: 9 1 2 5 4 5 4 2 5 9

2-5: 9 1 5 5 4 5 4 2 5 9

4-0: 9 1 5 5 4 5 4 2 5 4

5-9: 9 1 5 5 5 5 4 2 5 4

9-1: 9 5 5 5 5 5 4 2 5 4

==============================================================================

Question 3
Which of the following id[] array(s) could be the result of running the weighted quick union algorithm on a set of 10 items? Check all that apply.

4 6 0 4 4 4 0 4 5 4    4-7 6-1 0-2 5-8 3-4 5-7 9-8 2-1 2-4

7 9 9 3 6 6 1 6 5 9    Height of forest = 4 > lg N = lg(10)    

9 4 1 1 4 4 4 1 1 1    Size of tree rooted at parent of 1 < twice the size of tree rooted at 1

1 8 0 0 2 6 0 0 6 0    The id[] array contains a cycle: 1->8->6->0->1

0 1 0 7 4 5 0 7 8 9    0-2 6-2 7-3

Explanation / Answer

1)

class QuickFind
def initialize(n)
@ids = (0..n-1).to_a
end

def connected?(id1,id2)
@ids[id1] == @ids[id2]
end

def union(id1,id2)
id_1, id_2 = @ids[id1], @ids[id2]
@ids.map! {|i| (i == id_1) ? id_2 : i }
end

def display
puts @ids
end
end

qf = QuickFind.new 10
qf.union(8,3)
qf.union(9,4)
qf.union(0,7)
qf.union(2,4)
qf.union(1,7)
qf.union(1,2)
puts qf.display

2)

class WeightedUnion
def initialize(n)
@ids = (0..n-1).to_a
@sz = Array.new(n + 1, 1)
end

def connected?(first_node, second_node)
root(first_node) == root(second_node)
end

def union(first_node, second_node)
i = root(first_node)
j = root(second_node)
if @sz[i] < @sz[j]
@ids[i] = j
@sz[j] += @sz[i]
else
@ids[j] = i
@sz[i] += @sz[j]
end
end

def display
puts @ids
end

def root(index)
while index != @ids[index]
index = @ids[index]
end
index
end

end

wu = WeightedUnion.new 10
wu.union(1,9)
wu.union(5,7)
wu.union(0,5)
wu.union(3,8)
wu.union(4,2)
wu.union(4,9)
wu.union(8,7)
wu.union(8,2)
wu.union(0,6)
wu.display

3)

To solve this one, I looked at each line individually and attempted to determine whether it could be a weighted quick union result. Weighted quick unions always connect the smaller tree to the larger one in order to minimize height (thus optimizing the efficiency of the root() method).

I was able to rule out 1 due to the size of three with parent node 9. I was able to rule out 2 because the height of the trees together is 4, which is more than log(N) (where N is 10, the size of the initial array). I was also able to eliminate 4, because the root array contains a cycle 9->7->3->8->9.

The final two (3 and 5) seemed more difficult to check. I decided that since I could not think of any reasonable explanation why these would not be possible, that they must be. I made the guess, and ultimately got the correct answer of 3 and 5

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.