# COMP582 Module 2 Problem Set solution

\$30.00

Original Work
Category:

## Description

Rate this product

1. [20 pts] Suppose that we choose 3 as our factor in the “Big Box Store”
algorithm. That is, when the stack is full we allocate 3x the amount of current
storage. What is the complexity of M operations in this case? [Big Oh answer].
2. [20 pts] Repeat question 2 with a factor of 11. That is, when the stack
is full, allocate 11x the current size.
What is the complexity of M operations in case where factor = 11?
3. [20 pts] For this problem, let i be the sets in a union/find problem.
Let f[i] be the find array associated with this union/find problem.
Draw the tree associated with the f array below:
i 1 2 3 4 5 6 7 8 9 10
———————–
f[i] 2 2 4 2 6 7 2 4 5 6
4. [20 pts] Can the find array of problem 5 be a result of running weighted
quick union?
Explain why this is impossible OR ELSE give a sequence of union-find
operations that produce the above table.
5. [20 pts] Suppose we introduce the “add_new_set()” operation. The
operation will return a new whole number corresponding to a new disjoint set.
This means that the number of nodes in our graph may change dynamically.
Assuming add_new_set is O(1), what is the complexity of a sequence of