Guidelines for M.Sc. and B.Sc. theses at the Chair of Algorithms and Data Structures

M.Sc. and B.Sc. theses are supposed to be pieces of scientific works. Here are some guidelines to some minimal standards required of any scientific work so that it deserves that name.

Title

As a minimum, a title should be informative. Think of it as the shortest way to say what you did in one short sentence. A secondary criterion is that it is catchy. This is not necessary, however, and sometimes hard to achieve. Also a catchy title should be informative. If you build a system, a typical title is the name of the system, followed by a colon, followed by a short description of what the system does.

Abstract

An abstract should be self-contained and understandable also to a non-expert. Think of it as the shortest way to say what you did in one paragraph. As a minimum, it should clarify the problem dealt with in the thesis, and the main results that were obtained. Optionally, you can add a sentence or two about the underlying techniques and how the thesis advances the state of the art.

Introduction

An introduction should be self-contained and understandable to a non-expert. Think of it as the shortest way to say what you did in a couple of pages. As a minimum, it should clarify the problem dealt with, the motivation for dealing with that problem, the main results, the main challenge and the line of attack used to overcome it, and how it advances the state of the art. In the abstract, you have only one or two sentences (if any) for each of these aspects. In the introduction, you have more space. For the problem statement, it is almost always a good idea to provide a figure or screenshot with a (carefully chosen) example.

Related Work

Most probably, other researchers have worked on the problem of your thesis, or highly related problem, before. Your thesis should include a section which summarizes the most relevant of these works. Typically this is Section 2, right after the introduction. For each of these works, it should be explained in a nutshell what they do, what they achieve, and how this differs from what you do in your thesis. This should be understandable without the need to actually read the paper. Think of each description as the shortest way to say this in one paragraph. When there is a lot of work about a particular topic / problem, it is ok to focus on the most recent / most advanced approaches.

Theoretical analysis

Most probably, your work will make use of some algorithms and data structures. Either your own, or such from previous work, or a combination of the two. In any case, provide information about the basic complexity of your algorithms, in particular their running time. Do this also if the the statement appears straightforward to you. For example, your algorithm may obviously be linear in the size of the input data. Anyway, say it!

Empirical analysis

Most probably, your work involves the implementation of an algorithm or data structure, or of a whole system. Whatever it is, your implementation should be thoroughly evaluated. The kind of evaluation depends on the nature of your problem. What is almost always of interest is running time = how long does it take to do whatever your code does. If there is a pre-processing phase, this should also be evaluated. If a lot of disk space and/or memory is consumed, that should also be evaluated. If there are existing approaches which can be used to solve your problem, compare to the best one of these approaches. If there is no solution yet for your problem, think of a simple baseline algorithm (= the straightforward solution) and compare to that. Do your evaluation on at least three different data sets of different kinds and sizes.

Future work

Most probably, your work will leave various open ends. Make a list of what could be done next to improve on what you did. For each item, give a short description of the possible improvement + an idea for how, in principle, it could be achieved. Also give an estimate for the necessary time to realize that improvement (hours, days, weeks, months). Order your list by importance / significance = the thing that should be improved next / gives the biggest improvement should come first.