Question

1. Time Complexity of Kruskal's Algorithm

Which best describes the relative time complexities of the pre-sorting and main parts of algorithm?

A) The time to pre-sort dominates

B) The main part dominates

C) The relationship depends on the sort and disjoint-set operations being used

D) Kruskal's algorithm doesn't use pre-sorting

2. Kruskal's Algorithm: Disjoint Set Operations

What are the number of calls to the respective disjoint set operations in Kruskal's Algorithm?

A) MAKE-SET O(V), FIND O(V), UNION (V)

B) MAKE-SET O(V), FIND O(V), UNION (E)

C) MAKE-SET O(V), FIND O(E), UNION (V)

D) MAKE-SET O(V), FIND O(E), UNION (E)

E) MAKE-SET O(E), FIND O(V), UNION (V)

F) MAKE-SET O(E), FIND O(V), UNION (E)

G) MAKE-SET O(E), FIND O(E), UNION (V)

H) MAKE-SET O(E), FIND O(E), UNION (E)

3. Inverse of Ackermann's Function

Which best describes the rate of growth of α(n), the inverse of Ackermann's function

A) iterated logarithm

B) logarithm

C) linear

D) quadratic

E) exponential

F) super-expoential

4. Disjoint Set Operations: Compressing Find

Which best describes the disjoint set operation Compressing Find

A) Add all keys along the path from given node to root and store in the root

B) Add all keys along the path from root to given node and store in the given node

C) Make each node along the path from given node to root point to the root

D) Make each node along the path from root to given node point to the given node

E) Make all leaf nodes point to the root

F) Make all nodes point to the root

  

Answer 1

1.

The pre-sorting takes O(ElogE) time

The main part takes O(logV)

so the time oto pre sort dominates

So option A is correct

2.

MAKE SET(V), FIND SET(V), UNION(E)

So option B is correct

3.

Inverse ackernann has a slow growth rate

The growth rate is linear

So option C is correct

4.

Make each node along the path from given node to root point to the root

So option C is correct