Lectures Efficient Algorithms and
Data Structures I Parallel Algorithms Lab Course Algorithm Design Courses for PhD Students Oberseminar

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:00–12:00, 5620.01.102 (102, Interims Hörsaal 2)
    
  • Friday, 10:00–12:00, 5620.01.102 (102, Interims Hörsaal 2)
• Exercises (web page):
  2 hours per week exercises accompanying the lectures
  • Monday, 16:00–18:00, MI 00.08.038 (Chintan Shah)
  • Tuesday, 14:00–16:00, MI 00.08.038 (Richard Stotz)
  • Thursday, 10:00–12:00, MI 00.08.038 (Richard Stotz)
  • Friday, 12:00–14:00, MI 00.13.009A (Chintan Shah)
• 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: Monday, 17 Feb 2014

• Whole document: [1-608] (lecture - print1 - print4)
• Part 1. Organizational Matters [2-14] (lecture - print1 - print4)
  1. Contents [11-11] (lecture - print1 - print4)
  2. Literatur [12-14] (lecture - print1 - print4)
• Part 2. Foundations [15-119] (lecture - print1 - print4)
  1. Goals [18-18] (lecture - print1 - print4)
  2. Modelling Issues [19-29] (lecture - print1 - print4)
  3. Asymptotic Notation [30-41] (lecture - print1 - print4)
  4. Recurrences [42-119] (lecture - print1 - print4)
     1. Guessing plus Induction [46-50] (lecture - print1 - print4)
     2. Master Theorem [51-66] (lecture - print1 - print4)
     3. The Characteristic Polynomial [67-91] (lecture - print1 - print4)
     4. Generating Functions [92-115] (lecture - print1 - print4)
     5. Transformation of the Recurrence [116-119] (lecture - print1 - print4)
• Part 3. Data Structures [120-428] (lecture - print1 - print4)
  1. Dictionary [125-300] (lecture - print1 - print4)
     1. Binary Search Trees [126-135] (lecture - print1 - print4)
     2. Red Black Trees [136-160] (lecture - print1 - print4)
     3. AVL-Trees [161-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-300] (lecture - print1 - print4)
  2. Priority Queues [301-362] (lecture - print1 - print4)
     1. Binary Heaps [308-317] (lecture - print1 - print4)
     2. Binomial Heaps [318-337] (lecture - print1 - print4)
     3. Fibonacci Heaps [338-362] (lecture - print1 - print4)
  3. Union Find [363-391] (lecture - print1 - print4)
  4. van Emde Boas Trees [392-428] (lecture - print1 - print4)
• Part 4. Flows and Cuts [429-543] (lecture - print1 - print4)
  1. Introduction [430-439] (lecture - print1 - print4)
  2. Augmenting Path Algorithms [440-469] (lecture - print1 - print4)
     1. The Generic Augmenting Path Algorithm [440-452] (lecture - print1 - print4)
     2. Shortest Augmenting Paths [453-463] (lecture - print1 - print4)
     3. Capacity Scaling [464-469] (lecture - print1 - print4)
  3. Flow Applications [470-486] (lecture - print1 - print4)
     1. Matching [470-476] (lecture - print1 - print4)
     2. Baseball Elimination [477-482] (lecture - print1 - print4)
     3. Project Selection [483-486] (lecture - print1 - print4)
  4. Push Relabel Algorithms [487-521] (lecture - print1 - print4)
     1. Generic Push Relabel [487-507] (lecture - print1 - print4)
     2. Relabel to Front [508-515] (lecture - print1 - print4)
     3. Highest label [516-521] (lecture - print1 - print4)
  5. Mincost Flow [522-543] (lecture - print1 - print4)
• Part 5. Matchings [544-608] (lecture - print1 - print4)
  1. Definition [545-548] (lecture - print1 - print4)
  2. Bipartite Matching via Flows [549-552] (lecture - print1 - print4)
  3. Augmenting Paths for Matchings [553-562] (lecture - print1 - print4)
  4. Weighted Bipartite Matching [563-576] (lecture - print1 - print4)
  5. The Hopcroft-Karp Algorithm [577-586] (lecture - print1 - print4)
  6. Maximum Matching in General Graphs [587-608] (lecture - print1 - print4)