Problem Set 12

Consider a set whose elements are integers in the range $[0,N-1]$. A popular scheme for representing a set $A$ of this type is by means of a boolean array, $B$, where we say that $x$ is in $A$ if and only if $B[x]$ is true. Since each cell of $B$ can be represented with a single bit, $B$ is sometimes referred to as a bit vector.

1. Write the pseudocode to insert an element into set $A$, assuming that a bit vector $B$ is being used to store the data.
2. Write the pseudocode to delete an element from set $A$, assuming that a bit vector $B$ is being used to store the data.

---

Suppose I have a perfect skip list with the values 3, 4, 7, 12, 13, 14, 17.

3. Sketch a diagram of the skip list, showing which nodes are connected at which “levels”.
4. Sketch the path that would be taken through the skip list if you are searching for the number 12.
5. Sketch a diagram (or set of diagrams) that show how you would insert the number 15 into the skip list. You do not have to maintain a perfect skip list - the insertion of the element will make it non-perfect. Be sure to describe how randomness is used to determine the “height” of the new element.
6. Sketch a diagram (or set of diagrams) that show how you would remove the number 7 from the skip list. You do not have to maintain a perfect skip list - the deletion of the element will make it non-perfect.