AD1 Lectures & Slides
For administrative reasons, attendance at the first two-hour-lecture is mandatory: you must contact Pierre Flener if you cannot make it for a convincing case of force majeure, ideally in advance.
The main objective of lectures (föreläsningar) is to cover the required theoretical content
of the course, illustrated by as many examples as possible. Attendance is highly recommended. The essential aspects (in the eyes of the main instructor) of the course will be pointed out. Common misunderstandings will be discussed. The slides are not self-contained at all: they are only a support for the lectures, but not equivalent to their much more detailed content, so you ought to take notes.
There is no planned correspondence between the scheduled lectures and the topics of the course: a lecture may span two topics in the table below. Slides will be put on-line immediately before a lecture (but are not distributed in printed form), hence you can always figure out approximately where we currently are.
| Topic | Slides | Programs | Extra Material | Textbooks |
|---|---|---|---|---|
| Introduction | reminder on induction (slides 5-12) |
Chapter 1 of CLRS | ||
| Algorithm Analysis, Divide & Conquer, and Sorting | Slides, More Slides |
Programs | applet 1 for sorting, applet 2 for sorting |
Chapters 2, 3, 4, and 7 as well as pages 147-150 and Appendix D of CLRS; you may skip everything about invariants, little-oh, and little-omega, as well as Sections 4.6 and 7.3 |
| Stacks & Queues | Slides |
Programs | Pages 229-231 and Section 10.1 of CLRS | |
| Trees | Slides, AVL Slides |
Programs | applet 1 for AVL trees; applet 2 for AVL trees |
Sections B.5 and 10.4, as well as Chapter 12 of CLRS; you may skip Section 12.4; AVL trees are not covered in CLRS, but in Section 6.3 of L |
| Heaps | Slides |
Programs | applet for binomial heaps |
Chapter 6 and Problem 19-2 of CLRS; you may skip Section 6.4; binomial heaps are not covered in L |
| Hashing | Slides |
Chapter 11 of CLRS; you may skip Sections 11.3.3 and 11.5 |