Research

Online problems describe a special class of optimization problems in which algorithms must make decisions without knowing the entire input. Examples include cache management algorithms; these are designed to ensure that future requested data is present in the cache at the time of their request as often as possible.

From a theoretical standpoint, these algorithms are somewhat in the dark. However, in many practical scenarios, it is unrealistic to assume absolute ignorance of the input.

The model of advice complexity investigates to what extent additional information can be helpful in computing a solution in such a setting. Of particular interest in this context are lower bounds and sometimes very surprising threshold phenomena. For example, there are problems where a single bit of information helps to significantly improve the solution quality of an online algorithm, but each additional bit is no help at all until a certain non-constant value is reached.

In the context of many classical optimization problems, it is realistic to assume that certain properties of an optimal solution to be computed are already known. Consider, for example, a traffic network in which a certain structure is sought; for example, a Hamiltonian cycle of minimum cost.

If such a solution is given and there is a slight change in the initial situation, for example the network, the question arises whether a new solution to be computed can build on or make use of the already known solution.

In concrete terms, this means that a graph and a minimal Hamiltonian cycle are known; now a single vertex is added to the graph and a minimum Hamiltonian cycle is to be computed again for the resulting graph. Itriguingly, despite the intuitively very helpful additional information (the solution for a very similar graph), this problem is again NP-hard, but has a surprisingly good approximation algorithm.

Fortunately, it is becoming increasingly rare for computer science to be put on a level with mastering application software. Instead, the general educational character of computer science instruction is emphasized; the focus here is on "computational thinking," which is roughly understood as the mastery of various problem-solving strategies; for example, the ability to abstract, to represent information in a meaningful way, to decompose problems, and so on.

But how do you promote these competencies and how do you measure their acquisition? There has been some progress in recent years, particularly in the area of measurement tools; however, development is far from complete. Now the task is to design computer science lessons in such a way that problem-solving competencies are built up. This can only be done by developing instructional units and testing them in the classroom.

Obviously, this applied research is closely linked to the creation of teaching units and corresponding tools.

Especially in lower school classes, concepts of computer science have to be presented partly with a strong didactic reduction. For this purpose, metaphors are usually used that abstract from certain details.

However, many of these metaphors, for example "A variable in programming is like a drawer in which you can put things," can lead to misconceptions in the students, which may only become apparent later and then, already consolidated, lead to errors. The danger of certain misconceptions and possible manifestations should be recognized by the teacher so that she can address them.

In order to discover possible misconceptions, we look at students' solutions and investigate what concrete reasons for wrong answers might be.