Algorithms Lab (6 CP)

News

24.02.2009: Exam statistics:

26.11.2009: Due to the move of D-INFK from IFW to CAB the computer rooms E 31, E 37, and E 38 will be closed from 01.12.2009. Therefore the weekly exercise sessions will be held in the IFW C 31 and D 31 starting next week.

16.10.2009: During the last weeks the exercises sessions in the IFW building have been attended by only a few students. Thus, starting next Wednesday, we will offer only one room (IFW D 31). If the demand increases within the next weeks we will reopen IFW C 31.

30.09.2009: For questions related to some bugs in your solutions, please come to the exercise lectures on Wednesdays. If you need help before next Wednesday, use the forum on elabs.inf.ethz.ch.

28.09.2009: All necessary material, exercises and further information about the course can be found on https://elabs.inf.ethz.ch. For logging in use your NETHZ-Account. If you have questions please post in forum on elabs.inf.ethz.ch, come in the exercise sessions on Wednesday, or (just for exceptional cases) write an e-mail to algolab@lists.inf.ethz.ch.

Lecturer

Prof. Emo Welzl

Assistants

(If you really have to contact us, use algolab@lists.inf.ethz.ch!!! Usually a post in the forum on elabs.inf.ethz.ch will be answered quicker...)

Florian Jug

Christoph Krautz

Dr. Michael Hoffmann

Marek Sulovsky

Yann Disser

Rastislav Sramek

Time & Place

Tutorials: Monday, 17-19, CAB G 61

Exercises: Wednesday, 17-19, IFW C 31, D 31

Objective

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.

Prerequisites

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

Attendance

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.
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.

Content

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.

Exercises

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

Exam/Grades

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.

Synopsis

0. Introduction (Week 1)

Tutorial 1: Introduction to the working environment and the submission framework (online-judge).

1. Fundamental Algorithms (Week 2-4)

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

2. Algorithms on Graphs (Week 5-8)

Tutorial 2: Introduction to BGL

Tutorial 3: Flow algorithms - theory & BGL implementation

Tutorial 4: Planar graphs - theory & BGL implementation

3. Geometric Algorithms (Week 9-11)

Tutorial 5: Introduction to CGAL

Tutorial 6: Proximity structures

4. Linear Programming (Week 12)

Tutorial 7: Linear and quadratic programming - theory & CGAL implementation

5. Mixed Problems - practice sessions (Week 13-14)

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

Literature

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.

Links

• 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.