|
|
Past projectsExample of a successfully completed project: A Combinatorial Search with Dancing Links, by
Christopher Morgan, 1999/00. This project was successful in striking a good balance between theoretical analysis, algorithm design, and practical programming. I am looking forward to supervising similarly well-balanced projects in the future. |
My main areas of interest are algorithm design, parallel computation, presentation and teaching of mathematics. Here are some project ideas for 2003/04.
Implementing interesting algorithms on graphs. Recently I have been working on the Travelling Salesman Problem (TSP). Together with Dr. Vladimir Deineko (Warwick Business School), we designed an algorithm that approximates the optimal travelling salesman tour surprisingly well on a particular set of instances. An efficient implementation of this, and/or other TSP algorithms could make a very nice third-year project. The project will require an interest in theory, as well as practical programming skills.
Applying new programming techniques to ``hard'' combinatorial problems. For instance, one can apply linear optimisation methods to solve a real-life scheduling problem, such as timetabling the Spring term project presentations. An implementation could make use of existing linear optimisation software, e.g. Xpress-MP, or could be programmed in C or Java.
Studying and implementing parallel algorithms. One of the promising trends in parallel computing is the BSP model. Many interesting algorithms have been designed for this model, but relatively few of them implemented or studied from the practical point of view. In 2001/02 and 2002/03, I supervised a number of projects aimed at implementing and analysing BSP algorithms in a parallel programming environment. There is still plenty of work to do in this area, sufficient for several new projects. These projects will involve a substantial amount of background reading and good analytical skills.
Another possibility for a project on parallel computation is to view the BSP model from the programming, rather than algorithmic, angle. What BSP-based languages, tools and methods can we offer to a parallel application developer? Can we borrow any ideas from the ubiquitous Java? How well does the BSP model fit together with the object-oriented paradigm? Can one write functional BSP programs? Is the BSP philosophy of ``global order'' compatible with the complex, heterogeneous world of Internet and the Grid? These questions are very general, but your project can focus on one or two specific ideas. In 2002/03, I supervised a project aimed at creating a Java simulator of the BSP environment. This project can be extended in many ways, potentially leading to a few more projects.
Mathematical modules are an essential part of the computer science syllabus at any university. At Warwick, we teach introductory-level courses Mathematics for Computer Scientists and Discrete Mathematics I, as well as the more advanced courses Discrete Mathematics II and Logic for Computer Scientists. With student numbers ever increasing, effective feedback and coursework assessment becomes a major challenge. A great opportunity for a useful project is to look into ways of improving teaching and assessment using computers. In 2001/02, I supervised a project aimed at creating a Web-based mathematical message board, with an easy-to-use mechanism for exchanging formulas and proofs. I am looking for more interesting ideas in the area of computer-aided maths teaching.
Currently there are many interesting developments concerned with mathematical presentation in general. For many years (long before the Internet and HTML!), the LaTeX language has been a de-facto standard among mathematicians and computer scientists. The advent of HTML and XML opened up new possibilities, which are being realised in projects such as OpenMath and MathML. Would it be possible to use these new tools to represent algorithms, just as we can use them to represent ordinary mathematical objects?
Other ideas are welcome! I would be glad to hear any of your thoughts, especially ones related to the general areas above. You may also wish to consult the old version of this web page.
To get in touch with me, visit my contact page.
Home || Research | Publications | Teaching | CV | Contact
Teaching || Efficient Parallel Algorithms | Final year projects | Mathematics for Computer Scientists I | Personal tutees
Last updated on 11 May 2002
