Weekly Note 2, DM42, fall 2006
Lecture September 11
-
As announced in the previous weekly note, we will finish
the lecture material from the first lecture.
Discussion Section September 11
-
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.
-
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.
-
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).]
-
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.
-
Given n elements, how can a leftist heap be constructed in
time O(n)?
-
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.
-
[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
-
Recall (as announced earlier) that on September 13,
I am away for a conference, so that lecture is cancelled.
-
Note (as also announced earlier) that our meeting time on September 11
will be part lecture and part discussion section.
Last modified: Wed Sep 6 14:09:26 CEST 2006
Kim Skak Larsen
(kslarsen@imada.sdu.dk)