Weekly Note 2, DM42, fall 2006

Lecture September 11

Discussion Section September 11

  1. Repetition problems (pdf) on asymptotic notation and recursion equations. You would benefit from considering them all at home, but at the discussion section, we will only go through selected problems.
  2. Show that there is at most a logarithmic number of nodes on the right-most path in a leftist heap with n element.
    Hint: Show that a node of rank r has exponentially many nodes in its subtree. Then consider how ranks behave on the right-most path.
  3. Show that there is at most a logarithmic number of light nodes on the right-most path of a skew heap.
    [At the lecture, we showed that the complexity of meld is bounded by the number of light nodes on the right-most path, so meld is OA(log n).]
  4. Show that two standard heaps (as known from DM02) with 2p-1 elements each plus one extra element x can be combined into one heap in time O(p).
    Show that a standard heap can be build out of n=2p-1 elements in time O(n) by a bottom-up application of the result above.
  5. Given n elements, how can a leftist heap be constructed in time O(n)?
  6. How can the operations decreasekey, delete, and update be implemented to run in time O(log n) for leftist heaps? It is assumed that you are given a reference to the element and you may introduce additional references into the structure.
  7. [CLRS01] 17.3-3, 17.3-6, 17.3-7.
    Hint: in 17.3-7, you may assume that the median of n elements can be found in time O(n).
This lists all of the discussion section material for September 11 and September 18. We will discuss these problems in the order given here.

Announcements


Last modified: Wed Sep 6 14:09:26 CEST 2006
Kim Skak Larsen (kslarsen@imada.sdu.dk)