University of Waterloo
CS240 Winter 2020 Assignment 3
Due Date: Wednesday, March 4 at 5:00pm
Please read http://www.student.cs.uwaterloo.ca/~cs240/w20/guidelines.pdf for guidelines on submission. This assignment contains only written problems. Submit your written solutions electronically as a PDF with file name a3Submit.pdf using MarkUs. We will also accept individual question files named a3q1.pdf, a3q2.pdf, … , a3q5.pdf if you wish to submit questions as you complete them.
Problem 1 [0+5+2+3+3+3=16 marks]
a) Practice (not worth any marks): Starting with an empty skip list, insert the following
keys in order: 22 31 77 7 21 42 using the following flip sequence: HHTHTHHHTHHTHTHT
You should obtain the skip list given in the next part.
b) Given the following skip list:
+∞ 77 +∞ 77 +∞ S1 −∞ 7 21 22 31 42 77 +∞ S0 −∞ 7 21 22 31 42 77 +∞
S4 −∞
S3 −∞
S2 −∞ 7 22
Show the skip list that is created by inserting the keys: 37, 66, 13, 4, 27, 99 into the given skip list. You must use the following coin flip sequence:
HHHHTTHTHTHHTHTTHHHHHTHHTT
Note that each coin flip in the sequence will only be used once, in order and there may be some unused coin flips.
1
After inserting all keys, determine the exact number of comparisons (between 2 keys) required to search for the keys inserted in this part (that is, indicate what the search cost would be for 37, and then the search cost for 66, and so on).
For example, a search for 18 in the given skip list above, requires 6 comparisons.
For the remaining parts, assume that the probability of adding a level to a tower is p (0