Work Note 1, DM206, fall 2008

Lecture November 4

• Introduction.
• Prerequisites.
• Leftist Heaps [T83].
• Skew Heaps [W95].

Announcements

• The specific requirements for this course are the following:
  • Search Trees (red-black trees)
  • Priority Queues (binary heap)
  • Disjoint Sets (Galler-Fischer representation)
  • Asymptotic Notation
  • General Methods in Time and Space Analysis
  • Amortized Analysis
  Review this material as soon as possibly.
• Material will in general be distributed in class. You may come by my office at any time before the first lecture to pick up material (photocopies) for the first lectures.
• Note that I will maintain a list of used (distributed) material. There you can see where you find information about the various topics.