Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithms Lab HS2019

see also the corresponding entry in the course catalogue

News

Exam Statistics (Feb, 2020)

Grade Distribution

Contact

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

Lecturers

Prof. Angelika Steger

Assistants

Luca Di Bartolomeo,
Dr. Michael Hoffmann (contact),
Johannes Kapfhammer,
Fabian Lyck,
Asier Mujika,
Kalina Petrova,
Martin Raszyk,
Benjamin Schmid,
Pascal Su,
Tim Taubner,
Miloš Trujić,
Dr. Manuel Wettstein,
Xun Zou

Time & Place

MondayTuesdayWednesdayThursdayFriday
15-17 Assessment
Oct 15-Dec 10
CAB G15.2 / ML H34.3
Assessment
Oct 17-Dec 12
CAB G15.2 / ML H34.3
C++ Intro Exercises
Sep 20
CAB G61
Consulting
Sep 27-Oct 4
CAB G15.2
Consulting
Oct 11
CAB G61
Assessment
Oct 18-Dec 13
CAB G15.2
17-19 Problem of the Week
Sep 23-Dec 16
CAB H56+57 / HG E26.1 / anywhere
Tutorial
Sep 18-Dec 11
HG F7

The orange slots (individual performance assessments) are by appointment only. The blue slots (C++ intro and consulting hours) are completely optional and on demand only. Attendance/participation in the green slots (PotW and tutorials) is recommended. For more details see the section "Organization" below.

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 algorithms, and a working implementation in C++.

Prerequisites

Content

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

Organization

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

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.

Three times over the course of the semester every student is invited to an individual performance assessment. The assessment is performed as a one-on-one discussion with an assistant of at most 15min. that centers around a specific problem from the week(s) before. The problem to be discussed is known in advance, and the students should prepare to present both the problem and their solution attempt(s) to the assistant. As part of the discussion, the students receive feedback on where they stand, summarized in a grade on an integer scale from 0 (work in progress) to 2 (well done). In turn, the students give feedback on the same scale as to whether or not they found the assessment and the feedback they received helpful. The time slots for the individual performance assessments come in three windows of three weeks each, starting in Mid October. The administration and time management is handled by an electronic system.

Exam/Grades

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.

Every student who completes all three assessments (read: shows up at the specified time and completes the process by giving feedback to the assistant in the electronic system) receives a bonus in form of a quarter-grade (+0.25) on their grade from the final exam.

Synopsis

1. Fundamentals (Week 1-4) 2. Advanced Algorithms (Week 4-9) 3. Exam preparation (Week 10-14)

Technical Instructions

Please consult our technical FAQ to learn more about

Literature

Links