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)
Thursday, 10:00–12:00, MI HS2 - Exercises (web page):
2 hours per week exercises accompanying the lectures
Tuesday,14:15–15:45, MI 00.08.038 (Chintan Shah) or
Wednesday,10:15–11:45, MI 03.11.018 (Yutaka Nagashima) or
Thursday,12:30–14:00, MI 01.07.014 (Sudeep Kanav) or
Friday,12:15–13:45, MI 00.13.009A (Chintan Shah)
- Course Certificate:
- 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, 13 Feb 2013
- Whole document: [1-604] (lecture - print1 - print4)
- Part 1. Organizational Matters [2-13] (lecture - print1 - print4)
- Part 2. Foundations [14-118] (lecture - print1 - print4)
- Goals [17-17] (lecture - print1 - print4)
- Modelling Issues [18-28] (lecture - print1 - print4)
- Asymptotic Notation [29-40] (lecture - print1 - print4)
- Recurrences [41-118] (lecture - print1 - print4)
- Guessing plus Induction [45-49] (lecture - print1 - print4)
- Master Theorem [50-65] (lecture - print1 - print4)
- The Characteristic Polynomial [66-90] (lecture - print1 - print4)
- Generating Functions [91-114] (lecture - print1 - print4)
- Transformation of the Recurrence [115-118] (lecture - print1 - print4)
- Part 3. Data Structures [119-425] (lecture - print1 - print4)
- Dictionary [124-297] (lecture - print1 - print4)
- Binary Search Trees [125-134] (lecture - print1 - print4)
- Red Black Trees [135-159] (lecture - print1 - print4)
- AVL-Trees [160-183] (lecture - print1 - print4)
- Augmenting Data Structures [184-190] (lecture - print1 - print4)
- (a,b)-trees [191-203] (lecture - print1 - print4)
- Skip Lists [204-218] (lecture - print1 - print4)
- Hashing [219-297] (lecture - print1 - print4)
- Priority Queues [298-359] (lecture - print1 - print4)
- Union Find [360-388] (lecture - print1 - print4)
- van Emde Boas Trees [389-425] (lecture - print1 - print4)
- Dictionary [124-297] (lecture - print1 - print4)
- Part 4. Flows and Cuts [426-539] (lecture - print1 - print4)
- Part 5. Matchings [540-604] (lecture - print1 - print4)
- Definition [541-544] (lecture - print1 - print4)
- Bipartite Matching via Flows [545-548] (lecture - print1 - print4)
- Augmenting Paths for Matchings [549-558] (lecture - print1 - print4)
- Weighted Bipartite Matching [559-572] (lecture - print1 - print4)
- The Hopcroft-Karp Algorithm [573-582] (lecture - print1 - print4)
- Maximum Matching in General Graphs [583-604] (lecture - print1 - print4)