Skip to content

Latest commit

 

History

History
66 lines (48 loc) · 2.53 KB

21.2.md

File metadata and controls

66 lines (48 loc) · 2.53 KB
Raw

Exercises 21.2-1

Write pseudocode for MAKE-SET, FIND-SET, and UNION using the linked-list representation and the weighted-union heuristic. Assume that each object x has an attribute rep[x] pointing to the representative of the set containing x and that each set S has attributes head[S], tail[S], and size[S] (which equals the length of the list).

Answer

MAKE-SET(x):
	Initialize a new linked list
	Insert node x

FIND-SET(x):
	return rep[x]
	
UNION(x, y):
	Let smallist,biglist be the list with less and larger list according to size[x],size[y]
	put smallist to the tail in biglist

Exercises 21.2-2

Show the data structure that results and the answers returned by the FIND-SET operations in the following program. Use the linked-list representation with the weighted-union heuristic.

for i <- 1 to 16
	do MAKE-SET(x_i)
for i <- 1 to 15 by 2
	do UNION(x_i,x_i+1)
for i <- 1 to 13 by 4
	do UNION(x_i, x_i+2)
UNION(x1,x5)
UNION(x11,x13)
UNION(x1,x_10)
FIND-SET(x2)
FIND-SET(x9)

Assume that if the sets containing xi and xj have the same size, then the operation UNION(xi, xj) appends xj's list onto xi's list.

Answer

All x are in the same set, all return 1.

Exercises 21.2-3

Adapt the aggregate proof of Theorem 21.1 to obtain amortized time bounds of O(1) for MAKE-SET and FIND-SET and O(lg n) for UNION using the linked-list representation and the weighted-union heuristic.

Answer

MAKE-SET and FIND-SET can do in O(1) time, because MAKE-SET just initialize a new linked list and FIND-SET just return the representative of a linked list.

Theorem 21.1 said it took O(nlogn) time to update n objects, so in average take O(logn) time.

Exercises 21.2-4

Give a tight asymptotic bound on the running time of the sequence of operations in Figure 21.3 assuming the linked-list representation and the weighted-union heuristic.

Answer

T = O(n) + O(n) = O(n)

This example is the best case, because in each UNION, we only move one element.

Exercises 21.2-5

Suggest a simple change to the UNION procedure for the linked-list representation that removes the need to keep the tail pointer to the last object in each list. Whether or not the weighted-union heuristic is used, your change should not change the asymptotic running time of the UNION procedure. (Hint: Rather than appending one list to another, splice them together.)

Answer

UNSOLVED

Follow @louis1992 on github to help finish this task.