My preferences
- An individual software project is a software project, so I expect you to write a reasonably big functional piece of code.
- I am a big open-source fan, so I expect your resulting code should to be open-sourced and publicly available.
- I am also a big proponent of integration; if the project can be integrated into a bigger open-source project (like Sage or GLPK or anything, really) it most definitely should.
- I am quite open to any suggestions on a software project from your part. My interests are in the domain of theoretical computer science; so something that uses programming to solve a theoretical problem or bridges theory and practice is interesting to me. I will likely decline projects that better suited for another department.
Project suggestions
-
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.
-
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.