# 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:15–11:45, 5620.01.102 (102, Interims Hörsaal 2)
- Friday, 10:15–11:45, 5620.01.102 (102, Interims Hörsaal 2)

**Exercises**(web page):

2 hours per week exercises accompanying the lectures

- A01: Monday, 12:00–14:00, 00.08.038 (Stotz)
- A02: Monday, 12:00–14:00, 00.09.038 (Kohler)
- A03: Monday, 14:00–16:00, 03.10.011 (Sperr)
- B04: Tuesday, 12:00–14:00, 03.11.018 (Kohler)
- B05: Tuesday, 14:00–16:00, 00.08.038 (Matl)
- B06: Tuesday, 16:00–18:00, 00.08.036 (Sperr)
- C07: Wednesday, 10:00–12:00, 01.13.010 (Stotz)
- D08: Thursday, 10:00–12:00, 00.08.038 (Kraft)
- E09: Friday, 12:00–14:00, 00.13.009 (Kraft)
- E10: Friday, 14:00–16:00, 00.08.036 (Matl)

**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: Freitag, 10 Feb 2017

- Whole document: [1-599] (lecture - print1 - print4)
**Part 1.****Organizational Matters**[2-15] (lecture - print1 - print4)**Part 2.****Foundations**[16-120] (lecture - print1 - print4)- Goals [19-19] (lecture - print1 - print4)
- Modelling Issues [20-30] (lecture - print1 - print4)
- Asymptotic Notation [31-42] (lecture - print1 - print4)
- Recurrences [43-120] (lecture - print1 - print4)
- Guessing plus Induction [47-51] (lecture - print1 - print4)
- Master Theorem [52-67] (lecture - print1 - print4)
- The Characteristic Polynomial [68-92] (lecture - print1 - print4)
- Generating Functions [93-116] (lecture - print1 - print4)
- Transformation of the Recurrence [117-120] (lecture - print1 - print4)

**Part 3.****Data Structures**[121-390] (lecture - print1 - print4)- Dictionary [126-304] (lecture - print1 - print4)
- Binary Search Trees [127-136] (lecture - print1 - print4)
- Red Black Trees [137-161] (lecture - print1 - print4)
- Splay Trees [162-186] (lecture - print1 - print4)
- Augmenting Data Structures [187-193] (lecture - print1 - print4)
- (a,b)-trees [194-206] (lecture - print1 - print4)
- Skip Lists [207-221] (lecture - print1 - print4)
- Hashing [222-304] (lecture - print1 - print4)

- Priority Queues [305-361] (lecture - print1 - print4)
- Union Find [362-390] (lecture - print1 - print4)

- Dictionary [126-304] (lecture - print1 - print4)
**Part 4.****Flows and Cuts**[391-538] (lecture - print1 - print4)- Introduction [393-402] (lecture - print1 - print4)
- Augmenting Path Algorithms [403-432] (lecture - print1 - print4)
- Flow Applications [433-449] (lecture - print1 - print4)
- Push Relabel Algorithms [450-484] (lecture - print1 - print4)
- Mincost Flow [485-506] (lecture - print1 - print4)
- Global Mincut [507-522] (lecture - print1 - print4)
- Gomory Hu Trees [523-538] (lecture - print1 - print4)

**Part 5.****Matchings**[539-599] (lecture - print1 - print4)- Definition [540-540] (lecture - print1 - print4)
- Bipartite Matching via Flows [541-541] (lecture - print1 - print4)
- Augmenting Paths for Matchings [542-551] (lecture - print1 - print4)
- Weighted Bipartite Matching [552-565] (lecture - print1 - print4)
- Maximum Matching in General Graphs [566-587] (lecture - print1 - print4)
- The Hopcroft-Karp Algorithm [588-599] (lecture - print1 - print4)