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, 12:05–13:35, MI 00.13.009A
Thursday, 10:15–11:45, MI HS2 - Exercises (web page):
2 hours per week exercises accompanying the lectures
Tuesday, 14:00–16:00, MI 00.08.038
Teaching Assistant: Chintan Shah
- Course Certificate:
To successfully complete the module students must obtain at least 40% of the points on the written exam and also at least 40% of the points for the homework. - 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
- Whole document: [1-596] (lecture - print1 - print4)
- Part 1. Organizational Matters [2-13] (lecture - print1 - print4)
- Part 2. Foundations [14-103] (lecture - print1 - print4)
- Goals [15-15] (lecture - print1 - print4)
- Modelling Issues [16-26] (lecture - print1 - print4)
- Asymptotic Notation [27-32] (lecture - print1 - print4)
- Recurrences [33-103] (lecture - print1 - print4)
- Guessing plus Induction [36-40] (lecture - print1 - print4)
- Master Theorem [41-56] (lecture - print1 - print4)
- The Characteristic Polynomial [57-78] (lecture - print1 - print4)
- Generating Functions [79-101] (lecture - print1 - print4)
- Transformation of the Recurrence [102-103] (lecture - print1 - print4)
- Part 3. Data Structures [104-397] (lecture - print1 - print4)
- Dictionary [109-270] (lecture - print1 - print4)
- Binary Search Trees [110-119] (lecture - print1 - print4)
- Red Black Trees [120-143] (lecture - print1 - print4)
- AVL-Trees [144-167] (lecture - print1 - print4)
- (a,b)-trees [168-180] (lecture - print1 - print4)
- Skip Lists [181-193] (lecture - print1 - print4)
- Augmenting Data Structures [194-200] (lecture - print1 - print4)
- Hashing [201-270] (lecture - print1 - print4)
- Priority Queues [271-332] (lecture - print1 - print4)
- van Emde Boas Trees [333-368] (lecture - print1 - print4)
- Union Find [369-397] (lecture - print1 - print4)
- Dictionary [109-270] (lecture - print1 - print4)
- Part 4. Flows and Cuts [398-536] (lecture - print1 - print4)
- Introduction [399-408] (lecture - print1 - print4)
- Augmenting Path Algorithms [409-436] (lecture - print1 - print4)
- Push Relabel Algorithms [437-470] (lecture - print1 - print4)
- Flow Applications [471-487] (lecture - print1 - print4)
- Mincost Flow [488-504] (lecture - print1 - print4)
- Global Mincut [505-520] (lecture - print1 - print4)
- Gomory Hu Trees [521-536] (lecture - print1 - print4)
- Part 5. Matchings [537-596] (lecture - print1 - print4)
- Definition [538-541] (lecture - print1 - print4)
- Bipartite Matching via Flows [542-545] (lecture - print1 - print4)
- Augmenting Paths for Matchings [546-555] (lecture - print1 - print4)
- Weighted Bipartite Matching [556-567] (lecture - print1 - print4)
- The Hopcroft-Karp Algorithm [568-575] (lecture - print1 - print4)
- Maximum Matching in General Graphs [576-596] (lecture - print1 - print4)