3.3 Space-Efficient Doubly-Linked-Lists Recall that a space efficient doubly-linked list implements the List interface by storing a sequence of blocks (arrays) each containing b +/- 1 elements. 1. What is the running-time of get(i) and set(i) in a space-efficient doubly-linked list? 2. What is the amortized running time of the addi) operation in a space-efficient doubly-linked list? 3. In a space-efficient doubly-linked list containing n elements, what is the maximum amount of space that is not devoted to storing data? 4: Skip Lists Recall that a skiplist stores elements in a sequence of smaller and smaller lists Lo, ..., Lk. Lj is obtained from Li-1 by tossing a coin for each element in Li-1 and including the element in Li if that coin comes up heads. 1. Draw an example of a skiplist select a few elements and show the search paths for these elements 2. Explain how the reverse search path is related to the following experiment: Toss a coin repeatedly until the first time the coin comes up heads. 3. If there are n elements in Lo, what is the expected number of elements in Li? What about in Li? 4. If there are n elements in Lo, give an upper bound on the expected length of the search path for any particular element. 5. Explain, briefly, how a skiplist can be used to implement the SortedSet interface. What are the running times of operations add(x), remove(x), and contains(x)? 6. Explain, briefly, how a skiplist can be used to implement the List interface. What are the running times of the operations add(i,x), remove(i), get(i,x), and set(i,x). 3.3 Space-Efficient Doubly-Linked-Lists Recall that a space efficient doubly-linked list implements the List interface by storing a sequence of blocks (arrays) each containing b +/- 1 elements. 1. What is the running-time of get(i) and set(i) in a space-efficient doubly-linked list? 2. What is the amortized running time of the addi) operation in a space-efficient doubly-linked list? 3. In a space-efficient doubly-linked list containing n elements, what is the maximum amount of space that is not devoted to storing data? 4: Skip Lists Recall that a skiplist stores elements in a sequence of smaller and smaller lists Lo, ..., Lk. Lj is obtained from Li-1 by tossing a coin for each element in Li-1 and including the element in Li if that coin comes up heads. 1. Draw an example of a skiplist select a few elements and show the search paths for these elements 2. Explain how the reverse search path is related to the following experiment: Toss a coin repeatedly until the first time the coin comes up heads. 3. If there are n elements in Lo, what is the expected number of elements in Li? What about in Li? 4. If there are n elements in Lo, give an upper bound on the expected length of the search path for any particular element. 5. Explain, briefly, how a skiplist can be used to implement the SortedSet interface. What are the running times of operations add(x), remove(x), and contains(x)? 6. Explain, briefly, how a skiplist can be used to implement the List interface. What are the running times of the operations add(i,x), remove(i), get(i,x), and set(i,x)
