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)

Monday, 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: [1611] (lecture  print1  print4)
 Part 1. Organizational Matters [214] (lecture  print1  print4)
 Part 2. Foundations [15119] (lecture  print1  print4)
 Goals [1818] (lecture  print1  print4)
 Modelling Issues [1929] (lecture  print1  print4)
 Asymptotic Notation [3041] (lecture  print1  print4)
 Recurrences [42119] (lecture  print1  print4)
 Guessing plus Induction [4650] (lecture  print1  print4)
 Master Theorem [5166] (lecture  print1  print4)
 The Characteristic Polynomial [6791] (lecture  print1  print4)
 Generating Functions [92115] (lecture  print1  print4)
 Transformation of the Recurrence [116119] (lecture  print1  print4)
 Part 3. Data Structures [120431] (lecture  print1  print4)
 Dictionary [125302] (lecture  print1  print4)
 Binary Search Trees [126135] (lecture  print1  print4)
 Red Black Trees [136160] (lecture  print1  print4)
 AVLTrees [161184] (lecture  print1  print4)
 Augmenting Data Structures [185191] (lecture  print1  print4)
 (a,b)trees [192204] (lecture  print1  print4)
 Skip Lists [205219] (lecture  print1  print4)
 Hashing [220302] (lecture  print1  print4)
 Priority Queues [303365] (lecture  print1  print4)
 Union Find [366394] (lecture  print1  print4)
 van Emde Boas Trees [395431] (lecture  print1  print4)
 Dictionary [125302] (lecture  print1  print4)
 Part 4. Flows and Cuts [432546] (lecture  print1  print4)
 Part 5. Matchings [547611] (lecture  print1  print4)
 Definition [548551] (lecture  print1  print4)
 Bipartite Matching via Flows [552555] (lecture  print1  print4)
 Augmenting Paths for Matchings [556565] (lecture  print1  print4)
 Weighted Bipartite Matching [566579] (lecture  print1  print4)
 The HopcroftKarp Algorithm [580589] (lecture  print1  print4)
 Maximum Matching in General Graphs [590611] (lecture  print1  print4)