Show that the worst-case time required by Version 1 algorithms for op- erations
ID: 3628764 • Letter: S
Question
Show that the worst-case time required by Version 1 algorithms for op-
erations on disjoint sets (i.e., Algorithms 3.6.4, 3.6.5, and 3.6.8 of the textbook) is
(n + m * min{m, n}), where there are n makeset operations and a total of m union
and findset operations.
Algorithm 3.6.4 Makeset, Version 1, This algorithm represents the set {i} as a one-node tree
Input: i
Output: None
makeset1(i) {
parent[i] = i
}
Algorithm 3.6.5 Findset, Version 1, This algorithm returns the root of the tree to which i belongs
Input: i
Output: None
findset1(i) {
while (i != parent[i])
i = parent[i]
return i
}
Algorithm 3.6.6, Mergetrees, Version 1, This algorithm recieves as input the roots of two distinct trees and combines them by making one root a child of the other root
Input: i, j
Output: None
mergetrees1(i, j) {
parent[i] = j;
}
Algorithm 3.6.8, Union, Version 1, This alogithm receives as input two arbitrary values i and j and constructs the tree that represents the union of the sets to which i and j belong. The algorithm assumes that i and j belong to different sets
Input: i, j
Output: None
union1(i,j) {
mergetrees1(findset1(i), findset1(j))
}
Explanation / Answer
i.e., Algorithms 3.6.4, 3.6.5, and 3.6.8 of the textbook) is ?(n + m * min{m, n}), where there are n makeset operations and a total of m union and findset operations. Algorithm 3.6.4 Makeset, Version 1, This algorithm represents the set {i} as a one-node tree Input: i Output: None makeset1(i) { parent[i] = i } Algorithm 3.6.5 Findset, Version 1, This algorithm returns the root of the tree to which i belongs Input: i Output: None findset1(i) { while (i != parent[i]) i = parent[i] return i } Algorithm 3.6.6, Mergetrees, Version 1, This algorithm recieves as input the roots of two distinct trees and combines them by making one root a child of the other root Input: i, j Output: None mergetrees1(i, j) { parent[i] = j; } Algorithm 3.6.8, Union, Version 1, This alogithm receives as input two arbitrary values i and j and constructs the tree that represents the union of the sets to which i and j belong. The algorithm assumes that i and j belong to different sets Input: i, j Output: None union1(i,j) { mergetrees1(findset1(i), findset1(j)) }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.