Personen: Prof. Dr. Tobias Friedrich, Dr. George Skretas
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

Programmable matter refers to any kind of matter that can algorithmically change its properties; such properties can include shape, color, size, etc. One futuristic vision of programmable matter is the T-1000 android from the terminator movies. One more concrete vision is matter that can change its shape so that it can be reused (in factories) instead of being thrown away or recycled. While all of that sounds nice, the field is still very young and our goal for this seminar is going to be more modest. In this seminar, we will focus on theoretical programmable matter models where the matter is represented by a graph embedded on a grid. Our goal is to investigate reconfiguration and computation problems on such graphs. The most basic problem in any programmable matter model is the following:” Given an initial shape A and a target graph B, compute a centralized or distributed algorithm that transforms shape A into shape B”.

In the first few lectures, we will give a brief overview on the main topics required to understand the papers we are going to read later on. Such topics include graph algorithms, distributed computing and basic notions from computational geometry. After this, every student (or small groups of students) will pick an open problem to work on. The problem can range from computing algorithms for some programmable matter model to implementing a simulator for a programmable matter model. We will be able to provide you with open problems ourselves but we encourage you to read the literature and find open problems yourselves. There will be weekly meetings where we will be discussing the problems and offering guidance. The final goal is to have each student write a technical report or a scientific paper based on their findings.

Please be aware that this course is taught in English. You can find information on the course in the moodle page.

There are no formal requirements to participate in this course. However, the students should be familiar with graph algorithms and are able to read and understand mathematically involved proofs.

The grade will be based on 60% on your scientific report / paper and 40% on your presentations (of both an existing paper, and of your new results).

We meet online weekly on Monday, at 15:15- 16:45 in room K-1.04.

The following persons are involved in this lecture: