Lectures Efficient Algorithms and
Data Structures I Randomized Algorithms Fundamental Algorithms Seminar Selected Topics in Efficient Algorithms Lab Course Algorithms for Programming Contests

Efficient Algorithms and Data Structures I

General Info

• Lecturer: Prof. Dr. Harald Räcke
• Module: IN2003, TUMonline
• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  core course, topic algorithms
• Time and Place:
  
  • Monday, 10:30–12:00, 5620.01.102 (102, Interims Hörsaal 2)
  • Friday, 10:15–11:45, 5620.01.102 (102, Interims Hörsaal 2)
• Exercises (web page):
  2 hours per week exercises accompanying the lectures
  
  • Monday, 12:00–14:00, 00.08.038, Chintan Shah
  • Monday, 14:00–16:00, 00.08.055, Matthias Kohler
  • Tuesday, 14:00–16:00, 00.08.038, Dario Frascaria
  • Tuesday, 16:00–18:00, 00.08.036, Gregor Matl
  • Wednesday, 10:00–12:00, 01.13.010, Matthias Kohler
  • Thursday, 10:00–12:00, 00.08.038, Dario Frascaria
  • Friday, 12:00–14:00, 00.13.009A, Chintan Shah
  • Friday, 14:00–16:00, 00.08.036, Gregor Matl
• Course Certificate:
  To successfully complete the module students must obtain at least 40% of the points on the written exam.
• Audience:
  graduate students of computer science
  students with computer science as minor
• Prerequisites:
  1st and 2nd year courses
• Recommended for:
  Fundamental knowledge in topic Algorithms
• Related and Advanced Lectures:
  Efficient Algorithms and Data Structures II
  

Slides: Wednesday, 03 Feb 2016

• Whole document: [1-562] (lecture - print1 - print4)
• Part 1. Organizational Matters [2-13] (lecture - print1 - print4)
  1. Contents [10-10] (lecture - print1 - print4)
  2. Literatur [11-13] (lecture - print1 - print4)
• Part 2. Foundations [14-118] (lecture - print1 - print4)
  1. Goals [17-17] (lecture - print1 - print4)
  2. Modelling Issues [18-28] (lecture - print1 - print4)
  3. Asymptotic Notation [29-40] (lecture - print1 - print4)
  4. Recurrences [41-118] (lecture - print1 - print4)
     1. Guessing plus Induction [45-49] (lecture - print1 - print4)
     2. Master Theorem [50-65] (lecture - print1 - print4)
     3. The Characteristic Polynomial [66-90] (lecture - print1 - print4)
     4. Generating Functions [91-114] (lecture - print1 - print4)
     5. Transformation of the Recurrence [115-118] (lecture - print1 - print4)
• Part 3. Data Structures [119-388] (lecture - print1 - print4)
  1. Dictionary [124-302] (lecture - print1 - print4)
     1. Binary Search Trees [125-134] (lecture - print1 - print4)
     2. Red Black Trees [135-159] (lecture - print1 - print4)
     3. Splay Trees [160-184] (lecture - print1 - print4)
     4. Augmenting Data Structures [185-191] (lecture - print1 - print4)
     5. (a,b)-trees [192-204] (lecture - print1 - print4)
     6. Skip Lists [205-219] (lecture - print1 - print4)
     7. Hashing [220-302] (lecture - print1 - print4)
  2. Priority Queues [303-359] (lecture - print1 - print4)
     1. Binary Heaps [310-319] (lecture - print1 - print4)
     2. Binomial Heaps [320-339] (lecture - print1 - print4)
     3. Fibonacci Heaps [340-359] (lecture - print1 - print4)
  3. Union Find [360-388] (lecture - print1 - print4)
• Part 4. Flows and Cuts [389-503] (lecture - print1 - print4)
  1. Introduction [390-399] (lecture - print1 - print4)
  2. Augmenting Path Algorithms [400-429] (lecture - print1 - print4)
     1. The Generic Augmenting Path Algorithm [400-412] (lecture - print1 - print4)
     2. Shortest Augmenting Paths [413-423] (lecture - print1 - print4)
     3. Capacity Scaling [424-429] (lecture - print1 - print4)
  3. Flow Applications [430-446] (lecture - print1 - print4)
     1. Matching [430-436] (lecture - print1 - print4)
     2. Baseball Elimination [437-442] (lecture - print1 - print4)
     3. Project Selection [443-446] (lecture - print1 - print4)
  4. Push Relabel Algorithms [447-481] (lecture - print1 - print4)
     1. Generic Push Relabel [447-467] (lecture - print1 - print4)
     2. Relabel to Front [468-475] (lecture - print1 - print4)
     3. Highest Label [476-481] (lecture - print1 - print4)
  5. Mincost Flow [482-503] (lecture - print1 - print4)
• Part 5. Matchings [504-562] (lecture - print1 - print4)
  1. Definition [505-505] (lecture - print1 - print4)
  2. Bipartite Matching via Flows [506-506] (lecture - print1 - print4)
  3. Augmenting Paths for Matchings [507-516] (lecture - print1 - print4)
  4. Weighted Bipartite Matching [517-530] (lecture - print1 - print4)
  5. Maximum Matching in General Graphs [531-552] (lecture - print1 - print4)
  6. The Hopcroft-Karp Algorithm [553-562] (lecture - print1 - print4)