Weekly Note 4, DM42, fall 2006

Discussion Section September 25

  1. Remaining problems from last week.
  2. Sometimes we are interested in having a next operation which, given a reference to an element, returns a reference to the element with the next higher key. How could this be implemented in a tree structure such as red-black trees, for example. How would it be done for skip lists?
  3. Consider the details around maintaining maxLevel for skip lists, i.e., when and how to change it, and how to make sure that the complexity bounds (which are based on L(n)) still hold.
  4. At the lecture, we discussed the implementation of meld and split for skip lists, and how maxLevel should be adjusted to be close to L(n). However, in order to compute L(n) we need to know n. How can you add and maintain information to the skip list structure such that n can always be determined in expected time O(1)?
  5. Consider a standard binary heap. Is it possible to make an O(n) traversal of the heap and print all the priorities in non-decreasing order during that traversal? Argue your position.

Lecture September 27

Announcements


Last modified: Wed Sep 20 15:30:00 CEST 2006
Kim Skak Larsen (kslarsen@imada.sdu.dk)