# Teaching

## Algorithm Design and Analysis

Spring Term 2015

University of Zurich

#### News

- Solutions to exercises are posted, see below
- Exercise 3 is rescheduled to 19.5., Chapter 6 is removed.
- The exercises for the course are out. See download section below.
- We have a replacement lecture for the one that needed to be rescheduled. See also updated schedule below. Date: 12.3. Time: 8:00-9:30. Room: BIN 2.A.01.

#### Details

- Instructor: Dr. Alexander Souza, email: me@alexsouza.ch
- Room: BIN 2.A.01
- Lecture
- Tuesday: 8:00-9:30

- Exercises
- Announced in the schedule below
- Hand-in of sheets either before the exercise session or by email.

- ECTS-Credits: 3
- Prerequisites: None.
- Prior Knowledge: Informatik II: Algorithms and Datastructures. Some prior knowledge of graph theory and/or discrete mathematics is helpful, but not required.
- Language: English
- Lecture Notes: Published in the "Course Material" section below.
- Exam
- Type: Written exam, 90 minutes
- Date: 9.6.2015
- Time: 8:00 - 10:00
- Location: BIN 2.A.01
- Allowance: One sheet of paper with arbitrary handwritten content on both sides
- Admission: Half of the exercise problems must be worked on (serious attempt) for admission to the exam.
- Style: Proofs and analysis could be asked. There will be a section with short/multiple choice questions.

#### Objectives

This lecture covers advanced design principles for algorithms. The analysis will also be an important and integral part. That is, we will not only state the properties of an algorithm, e.g. its correctness or running time, but also prove them mathematically. In particular, we want to treat the following topics: Greedy Algorithms, Matchings, Network Flows, Dynamic Programming, (Integer) Linear Programming, Approximation Algorithms (for Knapsack and Scheduling).

In the tutorials, we will also work with state-of-the-art optimization software, e.g., ILOG CPLEX.

#### Contents

- Introduction: Examples, Combinatorial Optimization Problems, Linear Programming, Approximation Algorithms, Randomized Algorithms
- Greedy: Minimum Spanning Trees, Set Cover
- Network Flows: Maximum Flows and Minimum Cuts, Edmonds-Karp Algorithm, Minimum Cost Flows
- Matchings: Maximum Matchings, Blossom Algorithm
- Knapsack: Greedy, Dynamic Programming, Fully Polynomial-Time Approximation Scheme

#### Course Material

- Introduction Slides
- Lecture Notes
- Exercises
- Solutions:

#### Schedule

Date
| Type
| Contents |

17.2. | L | Chapter 1 - Introduction |

24.2. | - | LECTURE MUST BE RESCHEDULED: Chapter 2 - Greedy |

3.3. | L | Chapter 2 - Greedy |

10.3. | L | Chapter 2 - Greedy |

12.3. | T | Exercise 1 |

17.3. | L | Chapter 3 - Network Flows |

24.3. | L | Chapter 3 - Network Flows |

31.3. | L | Chapter 3 - Network Flows |

14.4. | T | Exercise 2 |

21.4. | L | Chapter 3 - Network Flows |

28.4. | L | Chapter 4 - Matching |

5.5. | L | Chapter 4 - Matching, Chapter 5 - Knapsack |

12.5. | L | Chapter 5 - Knapsack |

19.5 | T | Exercise 3 |

26.5. | L | Chapter 5 - Knapsack |

9.6. | X | Exam |

L: Lecture, T: Tutorial, X: Exam, -: Nothing

#### Software and Tutorials

Published here (password protected)

## Further Reading

- Korte, Vygen: Combinatorial Optimization, Springer Verlag
- Vazirani: Approximation Algorithms, Springer Verlag
- Cormen et al. – Introduction to Algorithms
- Mitzenmacher, Upfal – Probability and Computing