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

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


Course Material


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