Computer Science 409: Homework 5

Homework 4: Handed out: 3/1/01; Due: 3/13/01
(*Note that you have 12 days for this assignment, because of the test next week.*)

Section   Number   Points    Comments
22.3 	   1 	    8 	     Show the trees that result after each of lines 4,6, 8-11
23.1 	   3        4 	     You can describe the algorithms in English
23.2 	   1 	    4 	     Just state pi[v] and d[v] for every vertex after running BFS-Search[3]
23.2 	   3 	    4 	     Say which line(s) in the BSF algorithm presentedin class change (and how)
			     and then state the running time
23.2 	   6 	    6
23.3 	   2 	    5 	     Just state d[u] and f[u] for every vertex u
                             (no need to give the classification)
23.3 	   9 	    5
23.4 	   5 	    6

Additional question:

1.

[6 points] Show that if we have a sequence S of K MAKE-SETs + M FINDs + N UNIONs, where all the FINDs are performed at the end (after the MAKE-SETs and the UNIONs), then the running time of the algorithm (with path compression) is O(M + N + K). (Note that the algorithm doesn't change, just the analysis. Also note that we using UNION as defined in lecture, not as defined in the text.)