Project Ideas

Written by Holger Dell in January 2019, last modified in September 2021.
Estimated reading time: 10 minutes.

Overview

Who is this document for?

This document is intended for students at Goethe University who want to write a Bachelor/Master thesis in the theoretical computer science group.

Project Types

Depending on your interests and talents, different types of projects are possible:

Often, there is some overlap between different types.

Implementation and Experimentation

In this type of project, you will:

Literature review

In this type of project, you will choose a topic in theoretical computer science and write a literature review of existing research on this topic. This involves tracking down as many relevant papers and preprints on the topic as feasible, reading and understanding them, identifying the most important results as well as the most important open problems and goals of the research direction, and writing a comprehensive report. A project with a more limited scope could be to rewrite a specific proof from a research paper.

Problem-solving

In this type of project, you will prove new theorems in theoretical computer science. This could be upper bounds (algorithms, data structures) or lower bounds (hardness reductions, complexity). A project with a limited scope would be to analyze the proof of an existing theorem in a special case, and write it up as elegantly as possible. Problem-solving projects are much more challenging than a typical thesis project.

Themes and Topics

Depending on your interests and talents, different themes of project topics are possible: Theory, Engineering, Visualization, and AI Alignment.

Theory

Goal: perform a literature review or solve open problems in theoretical computer science.

What you get out of it:

What you need to bring:

Algorithmic Engineering

Goal: implement algorithms that may have never been implemented before! Test them rigorously, and compare their performance to other algorithms and implementations.

What you get out of it:

What you need to bring:

More specific aspects of a possible projects:

Software and benchmarks generated in your projects are developed under an open-source license, and when they’re ready will be published in a suitable outlet.

Visualization of Algorithmic Concepts

Goal: develop beautiful and easy-to-use educational visualizations of algorithmic and mathematical concepts. Make no mistake, the project should still include scientific writing in the form of a comprehensive Bachelor or Master thesis that describes the topic on a formal level, reviews the literature (both of the concept involved and its possibly pre-existing visualizations), discusses some experiments (maybe with different possible visualization and interaction patterns), and justifies your choices.

Examples: Past projects that are at the level of a Bachelor thesis include Algorithms with Albot, Color Refinement, and Graph Width Visualizer.

Non-examples: Your visualization project should do something new. For example, visualizing different sorting algorithms has been done before (a lot), so if that’s your proposal, you need to provide a very strong argument why your visualization idea is novel.

What you get out of it:

What you need to bring:

Since I want the results of visualization projects to be as accessible as possible, the applications will be browser-based and therefore use JavaScript (or a suitable other language, such as Python, in combination with WebAssembly). All products generated in your projects are developed under an open-source license, and when they’re ready will be publicly available.

More specific aspects of possible projects:

Links to existing visualization projects.

Human-aligned artificial intelligence

Goal: perform a literature review, or contribute to original research on the alignment problem. In particular, I would be most interested in connections to traditional, technical topics in theoretical computer science (algorithms, complexity, game theory, logics, cryptography). Topics such as “safe machine learning” are also possible.

What you get out of it:

What you need to bring:

Some introductory resources:

Supervision Process and Grading

As supervisor, I’m in a strange role conflict: During the project, I am your coach and want you to succeed, and in the end I’m expected to be an impartial referee and give you a grade. To reduce the stress level of everyone involved, let’s explicitly discuss some expectations upfront.

Timeline

Writing a Bachelor/Master thesis consists of several steps:

Choosing a topic

First, choose a type and theme for your project, and let me know in your first E-Mail which ones you’re interested in. What you choose should depend on your interests and career plans. For example, if you want to become a software engineer, then you can train your coding skills and build up your GitHub profile in Algorithmic Engineering or Visualization type projects, all while getting some exposure to algorithms research. If you want to do a PhD in a traditional subfield of computer science, mathematics, and/or physics, then, I would say, choose a topic in Theory or Algorithmic Engineering, or work on the Visualization of a highly non-trivial algorithm. If you want a low-risk topic that will be most likely to yield results within the given timeframe, choose a literature review, or an implementation project in Algorithmic Engineering or Visualization. In any case, choose something that you are genuinely excited about! Life’s too short.

Assuming that I have one ready, you can also ask me for a few topics. I will then briefly outline an initial, concrete project idea, and you can familiarize yourself with the relevant literature to some extent. You can also propose your own topic, but I’m picky. I want there to be some scientific component in your thesis, that is, it should rely on and refer to knowledge and skills that you have learned during your studies.

Project Plan

Before the project is started formally, I want you to design and agree with me on an informal project plan (1-2 pages). The plan describes the state-of-the-art, as well as general and specific goals for the project, and a rough timeline (I do not want a Gantt chart). The main benefits of the project plan are: 1) You learn what you are getting into by accepting the project, 2) during the project, you can come back to the plan to re-focus your efforts, and 3) it makes grading more objective in that grades will be determined based on how well the final outcome matches with the project plan. Of course, I know extremely well that plans can go wrong, so it is possible to change course if there is a good reason to do so—for example, if the original idea simply doesn’t work as expected.

Expectations

Your project is yours. It is not my responsibility to monitor your progress or to make sure that you get a good grade. That said, I will meet with you throughout the semester to discuss the project, make suggestions for improvements, and also give feedback on which aspects aren’t fully satisfactory yet. I will also be available electronically. If the project involves coding, I will do some code review. Every project involves scientific writing, and I will read and give feedback on your written drafts. However, I will not provide iterative feedback, because this would blur the line too much between you writing your thesis and me writing your thesis, so in total I will read and comment on at most one full draft so long as you present it to me with ample time before the deadline (at least two weeks).

Writing Advice

The Bachelor thesis is likely the first longer scientific text that you will write. There are many resources on the internet that can help you. Start with these:

I expect all my students to go to the schreibzentrum before they start their project. They provide individual help with planning your project and with writing your thesis.

In addition, you must follow these rules:

Formalities

If the project has not formally started yet, and I haven’t heard from you in three weeks, then I may give the topic to another student. (Note that formally starting the project requires several people signing a form, or the project being officially registered with the university.)

Lesen Sie den Paragraphen zu Bachelor/Masterarbeiten in Ihrer Studienordnung und übernehmen Sie Mitverantwortung dafür, dass er befolgt wird: § 35 in BSc Informatik 2019, § 25 in BSc Informatik 2012, § 34 in MSc Informatik 2019, oder § 35 in MSc Informatik 2015.