# 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.