Lectures Automata and formal languages Efficient Algorithms and
Data Structures I Randomized Algorithms Parallel 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:30–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 (Dario Frascaria)
  • Thursday, 10:00–12:00, MI 00.08.038 (Dario Frascaria)
  • 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: Friday, 23 Jan 2015

• Whole document: [1-611] (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-431] (lecture - print1 - print4)
  1. Dictionary [125-302] (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-302] (lecture - print1 - print4)
  2. Priority Queues [303-365] (lecture - print1 - print4)
     1. Binary Heaps [310-319] (lecture - print1 - print4)
     2. Binomial Heaps [320-339] (lecture - print1 - print4)
     3. Fibonacci Heaps [340-365] (lecture - print1 - print4)
  3. Union Find [366-394] (lecture - print1 - print4)
  4. van Emde Boas Trees [395-431] (lecture - print1 - print4)
• Part 4. Flows and Cuts [432-546] (lecture - print1 - print4)
  1. Introduction [433-442] (lecture - print1 - print4)
  2. Augmenting Path Algorithms [443-472] (lecture - print1 - print4)
     1. The Generic Augmenting Path Algorithm [443-455] (lecture - print1 - print4)
     2. Shortest Augmenting Paths [456-466] (lecture - print1 - print4)
     3. Capacity Scaling [467-472] (lecture - print1 - print4)
  3. Flow Applications [473-489] (lecture - print1 - print4)
     1. Matching [473-479] (lecture - print1 - print4)
     2. Baseball Elimination [480-485] (lecture - print1 - print4)
     3. Project Selection [486-489] (lecture - print1 - print4)
  4. Push Relabel Algorithms [490-524] (lecture - print1 - print4)
     1. Generic Push Relabel [490-510] (lecture - print1 - print4)
     2. Relabel to Front [511-518] (lecture - print1 - print4)
     3. Highest label [519-524] (lecture - print1 - print4)
  5. Mincost Flow [525-546] (lecture - print1 - print4)
• Part 5. Matchings [547-611] (lecture - print1 - print4)
  1. Definition [548-551] (lecture - print1 - print4)
  2. Bipartite Matching via Flows [552-555] (lecture - print1 - print4)
  3. Augmenting Paths for Matchings [556-565] (lecture - print1 - print4)
  4. Weighted Bipartite Matching [566-579] (lecture - print1 - print4)
  5. The Hopcroft-Karp Algorithm [580-589] (lecture - print1 - print4)
  6. Maximum Matching in General Graphs [590-611] (lecture - print1 - print4)