print · source · login   

Theme: Algorithms and Data Structures

If you like the course on Algorithms and Data Structures and want to do a project in this direction, there are several possibilities. Algorithm development plays a role in much of our research, and also companies often have to address algorithmic questions. Here are some general directions:

a) Model checking algorithms (BaSc, MSc)

In our research on model checking, we develop algorithms that establish automatically whether (a model of) some piece of software satisfies some property, for instance that certain bad states cannot be reached. Recently, we have become interested in analysing systems modeled as partially observable Markov decision processes (POMDPs). For more information see here. Contact Nils Janssen

b) Test selection algorithms (BaSc, MSc)

Suppose you are allowed to do a limited number of tests to figure out whether a piece of software is correct. Which tests will you do? In our research on conformance testing we work on smart algorithms for selecting tests. For more information, see e.g. here and here. Contact: Frits Vaandrager or Jan Tretmans

c) Algorithms for solving games and puzzles

For several puzzles (Sudoku, MasterMind, ..) one can wonder how hard they are to solve. A standard level of hardness is NP-completeness, and for many puzzles one can prove they are NP-complete. Coming up with a puzzle of your own choice and investigate its complexity class is a nice topic for a bachelor project. Similarly, one may investigate whether some configuration in a particular game has a winning strategy. In 2017 PSPACE completeness of a particular variant of five-in-a-row was investigated by Laurens Kuiper as his bachelor project. Despite the bad worse case complexity, smart algorithms and SAT/SMT solvers may still be deployed to solve the puzzles in practice. Contact: Hans Zantema