Department of Computer Science | Institute of Theoretical Computer Science

**Exam Statistics (Feb 24, 2017)**

For questions on exercises use the forums on moodle. For administrative questions or for reporting technical problems (with moodle or the judge), use algolab@lists.inf.ethz.ch.

Prof. Angelika Steger, Prof. Emo Welzl, Prof. Peter Widmayer

Andreas Bärtschi, Daniel Graf, Dr. Michael Hoffmann, Frank Mousset, Antonis Thomas, Nemanja Škorić, Dr. Przemysław Uznański, Felix Weissenberger, Manuel Wettstein

**Tutorials:** Wednesday, 17-19, CAB G 61 (first tutorial: Sep 21, 2016)

**Problem of the week:** Monday, 17-19, CAB H 56, CAB
H 57, HG E 26.1, or anywhere else (first PotW: Sep 26, 2016)

**Consulting hours:** Wednesday, 19-, CAB G 61 (after the tutorial)

see also: vvz.ethz.ch

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, BGL, and CGAL.

- Basic algorithms and data-structures. (details)
- Basic programming knowledge.

In this course students learn how to solve algorithmic problems given by a textual, story-like 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 practice their skills by solving weekly exercises. For that they have to understand the problem setting, find an appropriate modeling, choose suitable algorithms, and implement them using C/C++, STL, BGL, and CGAL. 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.

This course is a lab: Most of
the time is spent **working individually** on the given
problems.

In addition there is a weekly **tutorial**. These
tutorials are not lectures in the classical sense. In particular we will not
present theory and proofs there. Instead we rely on the corresponding knowledge
gained during your Bachelor studies. The tutorials serve

- to introduce technical concepts related to the programming environment and the software libraries that students may use in their programs,
- to discuss possible solutions to problems from the preceding week, and
- to provide examples and discuss problem solving strategies.

Occasionally we will work with algorithms and data structures that the students may not have encountered during their Bachelor studies. Such algorithms and data structures will be properly introduced in the tutorials, with a focus on applications rather than on the underlying theory.

Every Wednesday after the tutorial we will hand out **problem
sets**. The students hand in their solutions, using the online-judge, within one week.

Every Monday at 17:00 we post one problem as a
**"Problem of the Week"**. In order to score points for
this problem, only solutions that are submitted within the following two hours
are counted. The goal of this setup is to make students accustomed to exam
conditions and provide an early feedback of where they stand.

Finally, the assistants will be available for **consulting
hours** every Wednesday after the tutorial. These 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.

The grade of the course is solely based on the final exam. The exam takes place in a computer room, on two different days, 6 hours each, during the examination session. On both days you have to solve problems similar to those given during the semester.

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

**Tutorial 2: **BFS/DFS graph traversals; general
problem solving strategies: greedy and divide & conquer

**Tutorial 3:** Introduction to geometric computing in
CGAL

**Tutorial 4:** Introduction to graph representations
and algorithms in the BGL

**Tutorial 5: **Dynamic programming

**Tutorial 6:** Network flow algorithms in BGL

**Tutorial 7:** Linear and quadratic programming - Theory & the CGAL solver

**Tutorial 8:** Proximity structures in CGAL

**Tutorial 9:** Applications of network flows:
matchings and cuts

**Tutorial 10:** How to solve problems and prepare for
the exam, discussion of sample solutions

**Tutorial 11-13:** 3-fold problem sets (three similar
but different problems to solve during the tutorial)

**Tutorial 14:** Q&A session

Daniel Graf has compiled some information about the setup in the ETH student computer labs and instructions on how to setup the necessary software on your own computer.

Here is a virtualbox image that contains everything preinstalled.

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.

- 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.
- Online-judges with similar types of problems: acm.timus.ru, Spoj, TopCoder.
- VisuAlgo: animations of some data structures and algorithms: