Google Summer of Code 2010 ideas page

• Search tree visualiser

  A search tree visualiser can be used to look at the search tree Minion creates during search and identify possible sources of contention and insufficient propagation.

  The most basic form of such a visualiser would take Minion output and generate the search tree from it. It should also have a facility to hide irrelevant parts of the tree to make it feasible to look at large search trees.

  Improvements over a basic implementations might include: interactive exploration of the search tree, ability to save the visualisation to e.g. PDF, more sophisticated visualisations which make it easier to grasp all the information the search tree represents.

  There are several visualisers for other constraint solvers (Choco, Gecode, Eclipse) which could be used as a starting point. The visualiser can be implemented as a standalone program which reads Minion output or as a component of Minion that allows to control the search interactively.

  The visualiser should be cross-platform.

  Successful applicants should have strong programming skills in C++ or a language of their choice and experience in software engineering and testing. Experience in Computer Graphics and/or Artificial Intelligence is a plus, but not required.

  Mentors: Chris Jefferson, Karen Petrie, Lars Kotthoff

• Domain-specific search visualiser

  A domain-specific search visualiser shows the state of the search depending on the problem. For example for Sudoku, it would show a 9x9 grid with numbers in each cell.

  There exists a basic visualiser like that which shows the domains of variables in a grid (similar to Sudoku) written in Haskell. It could be used as a starting point. There are also domain-specific visualisers for other constraint solvers (Choco) which can be used as a guide.

  The final program should take a description of the type of visualisation and Minion output as inputs and produce a visualisation of the search process. Alternatively, it could be implemented as a part of Minion. It should have a set of predefined types of visualisation and allow to (easily) create new ones. It could also be made interactive and provide a facility for saving visualisations.

  The visualiser should be cross-platform.

  Successful applicants should have strong programming skills in Haskell/C++ or a language of their choice and experience in software engineering and testing. Experience in Computer Graphics and/or Artificial Intelligence is a plus, but not required.

  Mentors: Chris Jefferson, Karen Petrie, Lars Kotthoff

Our projects give you an exciting opportunity to work with researchers and explore and go beyond the boundaries of computer science. You will be able to bring your own ideas into the project and realise them. You will also be expected to work independently and deliver high-quality results.

All applicants should submit an outline of what they are planning to do specifically, possibly mentioning decisions such the programming language which to use and other implementation details. The application should convey an understanding of the problem and provide evidence that the applicant is capable of solving it.

If you have an idea for a project that is not listed here, but fits in with what we are doing, by all means let us know!

Prospective applicants are encouraged to discuss their application with Lars Kotthoff at larsko@cs.st-andrews.ac.uk.

For all projects, we require students to assign the copyright to us.