Department of Computer Science | Institute of Theoretical Computer Science

*Please do not
send email to any of the addresses below.* Instead, for questions
on exercises use
the forums on the course homepage. For questions on the
course formalities etc.,
use algolab@lists.inf.ethz.ch.

**First
tutorial: Wednesday Sep 19, 17-19, CAB G
61**

**Tutorials:** Wednesday,
17-19, **CAB G 61**

**Exercises:** Monday,
17-19, **CAB H 56, CAB H 57**

see also: vvz.ethz.ch

**Exam review
(Prüfungseinsicht): Feb 27 & Mar 7, 14:15, CAB
G15.2**

The objective of
this course is to learn how to solve a problem given by a textual
description. This includes appropriate problem modeling, choice of
suitable (combinatorial) algorithms, and implementing them using
C/C++, STL, CGAL,
and BGL.

- Basic
algorithms and data-structures. (details)
- Object-oriented programming.

The
exercise sessions are meant to offer a place to ask questions and get
help if you lack a necessary idea to solve a problem or if you
struggle with any other kind of course related
problem.

Attendance to the tutorials, as well
as to the exercise sessions, is not mandatory. It has to be mentioned,
though, that without attending the tutorials it might be more
difficult to find the solutions to the exercises given during the
course. Also potentially new problem solving strategies which are
crucial for your success in this course will be
presented.

In this course students learn how to solve algorithmic problems given by a textual description. We assume knowledge of elementary algorithms and data structures as they are typically taught on the Bachelor level; in tutorials we introduce more advanced algorithms and the usage of some standard libraries for combinatorial algorithms. Students are expected to practice their skills by solving weekly exercises. For that they will have to understand the problem setting, find an appropriate modeling, choose suitable algorithms, and implement them using C/C++, STL, CGAL, and BGL. The evaluation of the correctness and efficiency of their solutions will be performed by an online-judge which compiles the submitted source-code and runs it on a set of test instances. The response of the judge is one of the following: correct, partially correct (meaning that the program produced the correct answer for some of the test sets, but not for all), compilation error, run-time error, time limit error, memory excedance. While the goal is, of course, to write a program that passes all test instances (that is, even those which check extreme cases), in the exam - where the same online judge is used - partial credit will be given to programs that solve at least a standard problem set.

We will hand out weekly exercises each Monday. You are expected to hand in solutions, using the online-judge, by the following Monday.

During the exercise classes, we provide
help with the current exercises. For some of them, we will discuss
sample solutions during the tutorial classes two weeks after the
exercise was announced. There is no formal testat
requirement.

The grade of the course will be solely based on the final exam. This takes place as an online-exam on two days, 6 hours each, during the examination session. On each of the two days you'll get some problems in the spirit of the weekly exercises.

Solving elementary problems using C/C++, STL, and the algorithms and data structures listed here.

**Tutorial
1: **Introduction to the working environment and the submission
framework (online-judge) + Basics about how to program for this
lab.

**Tutorial 2: **Repetition of
essential data structures and
algorithms.

**Tutorial 3: **Repetition of
essential data structures and algorithms.

**Tutorial 4:**
Introduction to BGL

**Tutorial 5:** Flow
algorithms - theory & BGL
implementation

**Tutorial 6:** Planar graphs -
theory & BGL implementation

**Tutorial 7:** Introduction to
CGAL

**Tutorial 8:** Proximity
structures

**Tutorial 9:** Linear and quadratic
programming - theory & CGAL implementation

The
exercises of these weeks will be in the spirit of the
exam.

T. Cormen,
C. Leiserson, R. Rivest: *Introduction to Algorithms*, MIT
Press, 1990.

J. Hromkovic,
Teubner:*Theoretische Informatik*, Springer, 2004
(English: *Theoretical Computer Science*, Springer
2003).

J. Kleinberg, É. Tardos:*Algorithm
Design*, Addison Wesley,
2006.

H. R. Lewis,
C. H. Papadimotriou:*Elements of the Theory of
Computation*, Prentice Hall,
1998.

T. Ottmann, P. Widmayer:*Algorithmen
und Datenstrukturen*, Spektrum,
2002.

R. Sedgewick:** ***Algorithms in
C++: Graph Algorithms*, Addison-Wesley,
2001.

- ACM Programming Challenges Lab: This page provides some information regarding the exercises of the first part of the Algorithms Lab.

- The Boost Graph Library (BGL): Here you can download BGL and get information how to use it.
- Computational Geometry Algorithms Library (CGAL): Here you can download CGAL and get information how to use it.