Weekly Note 11, DM42, fall 2006

Discussion Section November 20

• We will discuss the following problem (try thinking about it in advance): We want to store fixed length tuples in a priority queue, e.g., if we decide on length three, we want to store data units of the form (x,y,z). Continueing the example of tuples of length three, we want operations deletemin1, deletemin2, deletemin3, which delete and return the tuple with the smallest first, second, or third tuple value, respectively. We are aiming at a solution as close to a heap as possible, and we are not willing to settle for a solution where we somehow use three copies of a heap to obtain the result.

Lecture November 22

• Balanced Trees and AVL-Trees [AFL05, AVL].
• Analysis of Red-Black Trees [DSST89, pages 110-111].
• Analysis of B-Trees ((a,b)-trees), if time permits.

Announcements

• The scheduled lecture on November 15 was cancelled and is now rescheduled for November 22.
• Announcement from IMADA: There will be a "pizza meeting" for all students of IMADA on Wednesday, Nov. 22 at 16:10-18:30 in room U49. At the meeting, IMADA will give general information on the Bachelor and Candidate studies, and specific information on the elective courses in Mathematics and Computer Science planned for the next semester. The meeting will end with a free pizza, beer, and soft drink session.