Computer Science 410: Homework 7

Note: ALWAYS explain what you are doing. The more information you give us, the easier it is for us to give you partial credit.

Homework 7: Handed out: April 1, due: April 8

Read Chapters 15, 19, 22.1-3, material on skip lists

Section     Number    Points    Comments
15.1	      5 	3
19.1 	      3 	3
19.1 	      4 	6
19.2 	      1 	7       Assume t=3
19.3 	      1 	6 	Again, t=3
22.3 	      1 	8 	Show the trees that result after each of lines 4,6, 8-11

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 Makesets and the Unions, then the running time of the Union-Find 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.)

2.

[6 points] Write pseudocode for deletion in a skip list. More precisely, write SKIPDELETE(S,k) which deletes all elements in the list with key k.