Department of Information Technology

AD2 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 online immediately before a lecture (but are not distributed in printed form), hence you can always figure out approximately where we currently are.

Topic Slides Extra Material CLRS Textbook
Introduction lec1.pdf Chapters 1 & 2, except Section 2.3
Growth of Functions & Recurrences lec2.pdf, Chapter01-03.pdf Chapters 3 & 4, except Section 4.4
Divide & Conquer, including Strassen's algorithm lec3.pdf Sections 2.3 & 28.2
Dynamic Programming lec15.pdf, Chapter15.pdf Sections 15.2 to 15.4
Elementary Graph Algorithms Chapter22.pdf Section B.4, pages 525-526, and Chapter 22
Greedy Algorithms lec16.pdf Section 16.2
Minimum Spanning Trees lec16.pdf applet for Prim's algorithm Chapter 23, but only Prim's algorithm
Single-Source Shortest Paths lec17.pdf applet for Dijkstra's algorithm Preamble of Chapter 24, and Section 24.3
Maximum Flow & Applications 08basicalgorithmsformaxflow.pdf, slides 1 to 14 of 09combinatorialapplicationsofmaxflows.pdf example of Ford-Fulkerson's algorithm Sections 26.1 to 26.3, but only Ford-Fulkerson's algorithm
Disjoint Sets Chapter21.pdf Sections 21.1 and 21.3
String Matching aalg13.pdf, Chapter32.pdf Sections 32.1 and 32.2

The un-annotated originals of the MIT OpenCourseWare slides by Prof.s Charles Leiserson and Erik D. Demaine are here (the lec*.pdf files), and the ones of Prof. James Orlin are here (the 0*.pdf files). The Chapter*.pdf files are based on prior versions by my colleagues Prof. Arne Andersson and/or Prof. Kemal Oflazer.

Updated  2009-10-21 11:25:02 by Pierre Flener.