# 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:
• Exercises (web page):
2 hours per week exercises accompanying the lectures

 Group Time Room Tutor Comment A01 Mo. 12:00 - 14:00 00.08.038 Stotz A02 Mo. 12:00 - 14:00 00.09.038 Guan A03 Mo. 14:00 - 16:00 02.09.023 Stotz B04 Tue. 10:00 - 12:00 00.08.053 Czerner B05 Tue. 14:00 - 16:00 00.08.038 Czerner C06 Wed. 10:00 - 12:00 03.11.018 Guan E07 Fr. 12:00 - 14:00 00.13.009 Stotz

• Course Certificate:
To successfully complete the module students must obtain at least 40% of the points on the written exam.
• Audience:
students with computer science as minor
• Prerequisites:
1st and 2nd year courses
• Recommended for:
Fundamental knowledge in topic Algorithms
Efficient Algorithms and Data Structures II

### help   Slides: Saturday, 22 Feb 2020

• Whole document: [1-525] (std · pr4 · pr1 · lec · two)
• Part 1. Organizational Matters [2-15] (std · pr4 · pr1 · lec · two)
1. Contents [12-12]
2. Literatur [13-15]
• Part 2. Foundations [16-120] (std · pr4 · pr1 · lec · two)
1. Goals [17-17]
2. Modelling Issues [18-28] (std · pr4 · pr1 · lec · two)
3. Asymptotic Notation [29-42] (std · pr4 · pr1 · lec · two)
4. Recurrences [43-120] (std · pr4 · pr1 · lec · two)
1. Guessing+Induction [47-51]
2. Master Theorem [52-67] (std · pr4 · pr1 · lec · two)
3. The Characteristic Polynomial [68-92] (std · pr4 · pr1 · lec · two)
4. Generating Functions [93-116]
5. Transformation of the Recurrence [117-120]
• Part 3. Data Structures [121-377] (std · pr4 · pr1 · lec · two)
1. Dictionary [126-291] (std · pr4 · pr1 · lec · two)
1. Binary Search Trees [127-136] (std · pr4 · pr1 · lec · two)
2. Red Black Trees [137-161] (std · pr4 · pr1 · lec · two)
3. Splay Trees [162-186] (std · pr4 · pr1 · lec · two)
4. Augmenting Data Structures [187-193] (std · pr4 · pr1 · lec · two)
5. Skip Lists [194-208] (std · pr4 · pr1 · lec · two)
6. Hashing [209-291] (std · pr4 · pr1 · lec · two)
2. Priority Queues [292-348] (std · pr4 · pr1 · lec · two)
1. Binary Heaps [299-308] (std · pr4 · pr1 · lec · two)
2. Binomial Heaps [309-328] (std · pr4 · pr1 · lec · two)
3. Fibonacci Heaps [329-348] (std · pr4 · pr1 · lec · two)
3. Union Find [349-377] (std · pr4 · pr1 · lec · two)
• Part 4. Flows and Cuts [378-524] (std · pr4 · pr1 · lec · two)
1. Introduction [380-389] (std · pr4 · pr1 · lec · two)
2. Augmenting Path Algorithms [390-418] (std · pr4 · pr1 · lec · two)
1. The Generic Augmenting Path Algorithm [390-401] (std · pr4 · pr1 · lec · two)
2. Shortest Augmenting Paths [402-412] (std · pr4 · pr1 · lec · two)
3. Capacity Scaling [413-418] (std · pr4 · pr1 · lec · two)
3. Flow Applications [419-435] (std · pr4 · pr1 · lec · two)
1. Matching [419-425]
2. Baseball Elimination [426-431]
3. Project Selection [432-435]
4. Push Relabel Algorithms [436-470] (std · pr4 · pr1 · lec · two)
1. Generic Push Relabel [436-456] (std · pr4 · pr1 · lec · two)
2. Relabel to Front [457-464] (std · pr4 · pr1 · lec · two)
3. Highest Label [465-470] (std · pr4 · pr1 · lec · two)
5. Mincost Flow [471-492] (std · pr4 · pr1 · lec · two)
6. Global Mincut [493-508] (std · pr4 · pr1 · lec · two)
7. Gomory Hu Trees [509-524] (std · pr4 · pr1 · lec · two)

### Annotated Slides

Note that naturally slides may contain errors. Please be aware that we cannot correct errors within annotated slides. Therefore please only use these slides for the annotations and refer to the above files for the rest.

• Fri, 18. Oct 2019
• Mon, 21. Oct 2019
• Fri, 25. Oct 2019
• Mon, 28. Oct 2019
• Fri, 01. Nov 20191
• Mon, 04. Nov 2019
• Fri, 08. Nov 2019
• Mon, 11. Nov 2019
• Fri, 15. Nov 2019
• Mon, 18. Nov 2019
• Fri, 22. Nov 2019
• Mon, 25. Nov 2019
• Fri, 29. Nov 2019
• Mon, 02. Dec 2019
• Fri, 06. Dec 2019
• Mon, 09. Dec 2019
• Fri, 13. Dec 2019
• Mon, 16. Dec 2019
• Fri, 20. Dec 2019
• Mon, 23. Dec 20191
• Fri, 10. Jan 2020
• Mon, 13. Jan 2020
• Fri, 17. Jan 20202
• Mon, 20. Jan 2020
• Fri, 24. Jan 2020
• Mon, 27. Jan 2020
• Fri, 31. Jan 2020
• Mon, 03. Feb 2020
• Fri, 07. Feb 2020
• 1no lecture
2missing due to system crash

February 2020: The Program Committee of SWAT 2020 is chaired by Susanne Albers.

February 2020: Susanne Albers is invited speaker at the ACM India Annual Event.

ESA/ALGO 2019 will be organized by Susanne Albers and her group.

May 2019: Susanne Albers is invited speaker at the symposium 50 Years Informatics

July 2019: Susanne Albers is invited speaker at SIROCCO 2019, Italy.

December 2017: Susanne Albers will give keynote address at the Graduation Day, Department of Computer Science at RWTH Aachen University.

April 2017: New Research Training Center AdONE, funded by the German Research Foundation.

Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.

August 2016: Susanne Albers is keynote speaker at Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.

Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and Literature, Mainz.

September 2015: Susanne Albers is invited speaker at MPI-INF – 25th Anniversary. The program features several Turing Award winners, Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.

June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form? organized by Erik D. Demaine (MIT) and MohammadTaghi Hajiaghayi (University of Maryland). 16th Conference on Electronic Commerce (EC15), Portland, Oregon.

##### Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707