Homework 6
Due Monday, April 5: on CourseSite, at 11:59pm
CSE 440: Spring 2021
1. We discussed in lectures how to augment RB-Trees to maintain dynamic order statistics. This question asks you to do the same for skip lists. Specifically, provide two different approaches to augment a skip list to maintain dynamic order statistics:
(a) The first approach is straightforward but may have a running time of the INSERT and DELETE operations that is asymptotically larger than the original skip-list (Hint: add a ”rank” field to each node).
(b) The second approach is more efficient and maintains the asymptotic running time of the INSERT and DELETE operations (Hint: add a ”size[]” field to each node x, such that x.size[i] is the number of elements in the skip list between x and its predecessor in level i that were not propagated to level i).
To simplify the problem, you can assume that each node has both forward and backward pointers that are maintained by both INSERT and DELETE operations (in other words, assume that each level is a doubly linked list).
For both approaches, you should follow the same procedure we discussed in lectures:
• Show how you would implement the OS-RANK operation, and state its time complexity (no formal proof is needed).
• Show how you would implement the OS-SELECT operation, and state its time complexity (no formal proof is needed).
• Show how you would maintain the new field during INSERT and DELETE operations.
No need to write a complete pseudo code for each operation. The overall idea and a brief informal justification why it works are enough (you can use figures/examples in your explanation). You can also ignore the corner cases like handling sentinel nodes.
1
2. Assume a hash table T[0..m-1] with a hash function h and chaining for collision resolution (assume uniform hashing). Suppose we are adding n elements z1, z2, …, zn, into T in that order (i.e., z1 is added first).
(a) Formally prove that the expected size of each chain is n/m
(Hint: select a fixed location 0 ≤ v < m, and define Xi = I{zi is added to slot v}).
(b) Compute the expected number of empty slots after adding z1,z2,...,zn into T (Hint: define Yi = I{location i is empty after adding z1,z2,...,zn into T}).
3. Show the Fibonacci heap that results from calling FIB-HEAP-EXTRACT-MIN on the Fibonacci heap shown in Figure 19.4(m) in the textbook.
4. Professor Pinocchio claims that the height of an n-node Fibonacci heap is O(lgn). Show that the professor is mistaken by exhibiting, for any positive integer n, a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of n nodes.
Please show details of your work to allow for possible partial credit.
2