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 4: Handed out: 2/22/01; Due: 3/1/01 (*note that the dates were wrong on the hardcopy*)

Read Chapters 7, 13, and 22

Section   Number    Points    Comments
7.1        1          2
	   2 	      3
	   3 	      2
	   4          3
           5 	      3        Explain why or why not
7.2 	   2          2
7.5 	   5          5
13.1 	   2          5
13.1 	   5 	      3
13.2 	   3 	      8        Hint: use the approach sketched in the lecture notes.
		 	       Prove the result carefully by induction.
13.2 	   4 	      8  

Extra question:

1.

[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.