Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Interdisciplinary Algorithms Lab, Fall Semester 2017

Instructors:

Prof. Dr. Angelika Steger
Prof. Dr. David Steurer
Dr. Johannes Lengler

First meeting:

The first meeting is postponed to Tuesday, September 26, at 17:15 in CAB G 15.2

In the rest of the semester, there will be a meeting every 1-2 weeks. On the first meeting, we will agree on a time slot for the rest of the semester.

Concept

In this course students will develop solutions for algorithmic problems posed by researchers from other fields. The course addresses master students in computer science, and is suited both for students with a theoretical and with a more applied focus.

The main goal is to learn how to solve algorithmic problems in an interdisciplinary or applied context. The key is to combine (i) a solid understanding of algorithmic methodology with (ii) insights into the problem at hand to judge which side constraints are essential and which can be loosened. Or, phrased differently, real world problems are often ill posed. And a major step toward a solution is to find an appropriate formalization of the problem.

The main focus of the course will be on finding an appropriate modelling. Since we are dealing with real data, performance will be evaluated experimentally. For this evaluation, students need to implement algorithms, preferably by using and combining available tools. The course will be run during the term. The course is 5KP and we thus expect that students work for the lab a full day each week.

Topic

The lab will be in cooperation with researchers from University of Zurich and University of Western Australia. Their project aims at understanding the cooperative behaviour of dolphins. To do this they collect behavioural data of free-living dolphins in Shark Bay in Western Australia. This data includes visual observations, from researchers and from drones, as well as corresponding audio recordings.
So far the researchers analyzed the audio files manually and identified times where whistles of dolphins occurred and tried to interpret the nature of the whistle. The aim of the lab is to automatize this task. As training data we have 100 hours of (labelled) audio recordings of dolphins.
The goal is to learn (i) to identify whistles and (ii) to recognize in particular so-called "signature whistles", that are characteristic for each individual dolphin.

Tentative Schedule

In the first week we will introduce the problem and provide access to the data. In the second week we will discuss possible modelling approaches and performance measures. During the first three weeks students will also (collectively) develop a tool box to for accessing and handling the data. In week 3 we will decide on the goals for a mid term competition. During weeks 4-7 students will develop solutions for the mid term competition in teams (2-3 students per team). Each team also has to hand in a written description of their solution (5-10 pages). The aim of this description is to make the approach available for all other student teams. In week 8 we will agree on the goals for the final competition (in week 15) for which each team will improve the solutions, using all building blocks that were presented in mid-term. With this setup students should learn that while, naturally, the quality of a solution should be as good as possible, a proper documentation is also essential. The success of a team will thus be viewed as a combination of the quality of the final solution and whether the building blocks presented at mid-term are used by other teams.

Cooperation

The lab aims at bringing together students with different skill sets. For example, a theoretically oriented student may be better at developing measures for the similarity of whistles, or at reading papers about signal processing, while a practically oriented student may have better programming skills, or may come up with efficient heuristics. The teams should be formed in such a way that the students complement each other with their skills and interests.