Skip to content

Latest commit

 

History

History
66 lines (48 loc) · 3.32 KB

21.2.md

File metadata and controls

66 lines (48 loc) · 3.32 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

For each member of the set, we will make its first field which used to point back to the set object point instead to the last element of the linked list. Then, given any set, we can find its last element by going ot the head and following the pointer that that object maintains to the last element of the linked list. This only requires following exactly two pointers, so it takes a constant amount of time. Some care must be taken when unioning these modified sets. Since the set representative is the last element in the set, when we combine two linked lists, we place the smaller of the two sets before the larger, since we need to update their set representative pointers, unlike the original situation, where we update the representative of the objects that are placed on to the end of the linked list.

Follow @louis1992 on github to help finish this task.