Skip to content

Latest commit

 

History

History
48 lines (33 loc) · 1.25 KB

21.3.md

File metadata and controls

48 lines (33 loc) · 1.25 KB
Raw

Exercises 21.3-1

Do Exercise 21.2-2 using a disjoint-set forest with union by rank and path compression.

Answer

					1
				
			/		|	\	   				\	
			2		3    5					9
			
					|	/ \			/    /		 \
					4   6 7		   10   11		 13
					
						  |				 |	   /   \
	   					  8  			12    14   15
	   					  
	   					  						    |
	   					  						    16

Exercises 21.3-2

Write a nonrecursive version of FIND-SET with path compression.

Answer

implementation

Exercises 21.3-3

Give a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, that takes Ω(m lg n) time when we use union by rank only.

Answer

reference

Exercises 21.3-4 *

Show that any sequence of m MAKE-SET, FIND-SET, and LINK operations, where all the LINK operations appear before any of the FIND-SET operations, takes only O(m) time if both path compression and union by rank are used. What happens in the same situation if only the path-compression heuristic is used?

Answer

UNSOLVED

Follow @louis1992 on github to help finish this task.