Weekly Note 1, DM42, fall 2006
Lecture September 6
-
Introduction.
-
Amortized Analysis [CLRS01] (sections 17.0-17.3).
-
Leftist Heaps [T83].
-
Skew Heaps [W95].
This lists all of the lecture material for September 6 and
September 11 (see below), i.e., we will not manage to cover
all of the listed material in this first lecture.
Announcements
-
As announced several places, first meeting time is September 6
at 12:15 in IMADA's seminar room.
Normal schedule will be lecture on Wednesday and discussion
section on the following Monday.
However, on September 13, I am away for a conference, so that lecture is
cancelled.
As a result of this, the time slot on Monday, September 11 will likely
be mixed lecture and discussion section.
-
It's a good idea to use the extra time Monday, September 4 to make
sure you have all the prerequisites up-to-date. You need the background
from a standard introductory algorithms and data structures course
such as DM02. More specifically, you should know as much as
possible about the following topics:
-
Search Trees (red-black trees)
-
Priority Queues (binary heap)
-
Disjoint Sets (Galler-Fischer representation)
-
Asymptotic Notation
-
Time and Space Analysis
-
Note that DM19 is not a prerequisite for this course. For that
reason, students who have taken DM19 will experience some repetition,
particularly during the first week of the course. In total, the overlap
between DM19 and DM42 will be less than 10%.
-
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 that lecture.
-
Note that I will maintain a
list of used (distributed) material.
There you can see where you find information about the various topics.
Last modified: Tue Sep 5 08:34:53 CEST 2006
Kim Skak Larsen
(kslarsen@imada.sdu.dk)