From the summer semester of 2015/2016, I am happy to act as an advisor for NPRG045 Ročníkový projekt (Individual Software Project), which is a mandatory part of the Bachelor's degree at MFF UK. If you are looking for a project, take a look at my ideas (or come up with your own) and send me an email to bohm(sign) afterwards.

My preferences

Project suggestions

  1. Lower bounds for online problems. An online problem is a problem where items arrive one by one (think of baggage arriving on a conveyor belt) and we have to immediately process such items (put them in a truck, assign them somewhere). We compare the efficiency of our algorithm to an algorithm that knows the entire sequence in advance.

    Such online problems can be actually modelled as two-player games; your algorithm packs the items as they come, and a malicious adversary keeps suggesting items so that your algorithm behaves poorly. This relation to two-player games also suggests an idea: we can solve limited instances of these games using minimax search! Even better, if we compute the game and adversary wins, this gives a lower bound for the general online problem.

    Indeed, this is a reasonable idea and it has been tried for some online problems, but not for all. The goal of this project is to find more online problems where we can use minimax to solve small instances, and get lower bounds for these problems.

    If successful, the project can be extended into a bachelor thesis.

  2. Improving open-source linear programming solvers. A linear programming solver is a tool for quickly computing optimal solutions to various optimization problems, modelled using a method called linear programming. These solvers usually also support a very similar method called integer programming, which can actually solve any NP-complete problem.

    If you do not know anything about linear programming, there is a mandatory class called "Optimization methods" for 2nd year students of MFF UK, so you will learn it very soon.

    There are some excellent commercial linear programming solvers out there, such as IBM CPLEX or Gurobi, but the best open-source offerings (such as GLPK) are slower and somewhat lacking in features.

    Our goal would then be to find a reasonably-sized omission in GLPK and implement it.