|
|
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, and teaching of mathematics. Here are some project ideas for 2002/03.
Launching a new attack on the tripod packing problem, described in Morgan's report above. By running a fairly simple C++ program, I have managed to obtain a packing which, I believe, is the densest currently known in the world. It is likely that with a little more work and some fresh ideas, even better results can be achieved. The project will require an interest in theory, as well as practical programming skills.
Applying new programming techniques to ``hard'' combinatorial problems. Designing parallel algorithms for combinatorial search is one example of this approach. Knuth's `` dancing links'' paper, used in Morgan's report, is another example. A project may consist, for instance, in extending the ``dancing links'' method, comparing it with other methods, applying it in a new context, or be inspired by ``dancing links'' in some other way.
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, I supervised two projects aimed at implementing and analysing BSP algorithms in a parallel programming environment. There is still plenty of work to do in this area. The project will involve a substantial amount of background reading and good analytical skills. This project is already taken.
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. For example, you can create a Java simulator of a BSP environment, and look at multithreading as a possible way of enhancing the basic BSP programming model. This project is already taken.
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, Mark ter Braak completed 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.
Other ideas are welcome! I would be glad to hear any of your thoughts, especially the ones related to the general areas above. To get in touch with me, visit my contact page.
Home || Research | Publications | Teaching | CV | Contact
Teaching || Parallel Algorithms | Final year projects | Discrete Maths I
Last updated on 6 June 2002
