logotyp Student Portal
Menuadmin.courses.matrix.content.exams.examinationType=Tentamenstyp
Web page

Algorithms and Data Structures II, 5.0 c

Course code:1DL231, Report code:11016, 33%, DAG, NML, week: 43 - 02 Semester: Autumn 2016

Lectures, Slides, and Textbook

Lectures & Slides

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 head teacher, 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 and study the extra material mentioned below; if you miss a lecture, then read the textbook instead.

There is no planned correspondence between the scheduled lectures and the topics of the course: topic starts and ends need not be aligned with lecture starts and ends. Slides will be put online 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 CLRS3 Textbook Teacher
Introduction 01-02.pdf   Chapters 1 & 2 Pierre Flener
Reminder: Growth of Functions, Recurrences, and Divide & Conquer 03-04.pdf, 04.pdf AD1/PKD-excerpts.pdf, 01-03.pdf Chapters 3 & 4, except Section *4.6 Pierre Flener
Dynamic Programming 15A.pdf15A27.pdf15B.pdf   Chapter 15 Pierre Flener
Greedy Algorithms 16+23.pdf   Chapter 16, except Sections *16.4 and *16.5 Pierre Flener
Minimum Spanning Trees 16+23.pdf visualisation of Prim's algorithm Chapter 23 (we only study Prim's algorithm) Pierre Flener
Single-Source Shortest Paths 24.pdf visualisation of Dijkstra's algorithm Chapter 24: pages 643-650 and Section 24.3 (we only study Dijkstra's algorithm) Pierre Flener
Maximum Flow 26A.pdf, 26ex.pdf visualisation of Ford-Fulkerson's algorithm Chapter 26 (we only study Ford-Fulkerson's algorithm), except Sections *26.4 and *26.5 Pierre Flener
Disjoint Sets 21.pdf visualisation Chapter 21 (we do not study the representation in Section 21.2), except Section *21.4 Pierre Flener
String Matching slides 1-14 + 27 of 32A.pdf, 32B.pdf   Chapter 32, except Sections 32.3 and *32.4 Pierre Flener
P versus NP 34.pdf talk by Prof. Michael Sipser Chapter 34 Pierre Flener

Given the availability of excellent lecture slides for the standard material of this course, there is no point and no resource for the head teacher to design his own slides. The non-annotated originals of the MIT OpenCourseWare slides by Prof.s Charles Leiserson and Erik D. Demaine on Chapters 1-24 are here, the ones of Prof. James Orlin on Chapter 26 are here, and the original location of the slides by Prof. Simonas Saltenis is here.  The files with the UU logo are based on prior versions by the former colleagues Prof. Arne Andersson and Prof. Kemal Oflazer of the head teacher.

Textbook

The following textbook, available as an e-book at ub.uu.se, is referred to as CLRS3 on this website:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Introduction to Algorithms (third edition). [errata]
The MIT Press, 2009.

We will use annotated versions of some slides of the MIT Open Course Ware available for this textbook.

There is on-line supplemental content (mostly reserved for teachers), including solutions to a select set of exercises and problems.

The second edition (errata) can also be used, but note that reading guidelines on this AD3 website refer to the third edition.