Group mailing list: gp-nza1.
Team members:
Project description:
This is a well-known problem. Given a rectangular area (2D suitcase) and some 2D convex shapes (circles, rectangles,..) pack them in the suitcase as tightly as possible. This has a real importance for manufacturing (cutting things out of a piece of material so that there is as little waste as possible).
You should also provide an interface for the user to draw the suitcase and shapes, and display the solution (with the option to display the packing process, too).
Group mailing list: gp-nza2.
Team members:
Project description:
A graph consists of a set of nodes (vertices) and links (edges) between them. Graphs are used to represent many different things, for example simplified route descriptions, states of an automaton, or stages in some process (e.g. the execution of a program).
Two graphs may look different and even have a different number of vertices, but still describe the same process. Such graphs are called bisimilar (which basically means that whenever you can follow some edge in one graph, you can follow a corresponding edge in another graph (and vice versa) and again arrive in "similar" positions). There exist algorithms which, given two graphs, determine whether the graphs are bisimilar or nor.
Write a program which allows the user to draw two graphs and check whether they are bisimilar.
Group mailing list: gp-hla1.
Team members:
Project description:
This project is to build a software system that can carry on a reasonable conversation with one or more people. The program should "learn" to speak by storing all conversations it encounters, using these stored conversations as its own database of conversation. For example, a person might express an opinion that the program encounters, and the program can later express that same opinion to another person, as if it was its own opinion.
The program will possibly make use of a language like LISP or Scheme and should use a database backend to store all the conversations. You will have to decide how to store and index conversation-pieces and how the program will decide which conversation-piece to use in reponse to something it reads. We will test this by asking real people to converse with the software.
Group mailing list: gp-hla2.
Team members:
Project description:
Write some software that packs up a credit card number using public-key encryption techniques. Write a Java applet to decrypt and one to encrypt. There will be a web page which has both encryption and decryption applets. The user gets the encryption applet, enters credit card number and date plus recipient email address and recipient's public key, then the applets encrypts the info and mails it to the recipient. The recipient can then download the decryption applet, put in their private key and it unpacks. Note that the credit card number and the private key are *never* openly sent across the Internet, they are only ever seen at either client's end. The Web page merely serves the applets, the rest is done at client end.
Group mailing list: gp-sdb1.
Team members:
Project description:
Inhabited Television is a new entertainment medium that combines audience participation in a TV show in a shared on-line virtual world with broadcasting the resulting action (via virtual cameras in the world) to a traditional viewing audience.
This project is to develop an on-line programme guide that people would access from their homes. Like a conventional TV guide, this would inform them of the programme schedules for different channels. However, it would also tell them about potential roles in the show that they might take up and would allow them to register an interest. Further software might then assign people to roles in the show (perhaps based upon their past experiences) and would configure their home machines and network to be ready to run at the appropriate time.
Group mailing list: gp-sdb2.
Team members:
Project description:
Inhabited Television is a new entertainment medium that combines audience participation in a TV show in a shared on-line virtual world with broadcasting the resulting action (via virtual cameras in the world) to a traditional viewing audience.
Creating an Inhabited TV show involves several stages such as: overall concept design, graphics design, game-play design, scripting, rehearsal and virtual world software configuration. This project will design and prototype a storyboard tool that allows producers and script writers to develop a show outline that can then be annotated by other designers and technician before eventually being fed into virtual world software.
Group mailing list: gp-dfb1.
Team members:
Project description:
Given the rapid growth of digital document availability, in formats such as HTML and PDF, publishers and librarians are increasingly looking to the Internet as a means of discovering documents and of delivering them to users (either free of charge or, perhaps, with some element of charging being involved).
But digital documents can be very large files indeed (particularly if high-resolution bitmaps are involved). For this reason there is great interest in using *metadata* (i.e. information about a document such as title, author, abstract, keywords, number of chapters etc.) as the first step in providing information to a user about that document, prior to any decision about whether to download it or not.
This project will take the "Electronic Publishing" corpus of papers (about 300 in all) and will prepare metadata descriptors for each paper via a script which analyses the Document Information of the final Acrobat documents. The task is then to prepare a Web based interface to this corpus which displays all of the corpus in a coherent and attractive way, via metadata, and which allows users to negotiate for downloading all or a part of any document on offer.
Group mailing list: gp-dfb2.
Team members:
Project description:
In recent months one of the most popular games on the Internet has been "The Six Degrees of Kevin Bacon" and it explores in a quantitative way the conjecture that Kevin Bacon is one of the best-connected bit-part actors in Hollywood (i.e. he's been in movies with just about everyone).
So if an actor has starred in a movie with Kevin Bacon his/her Bacon number is 1; if he/she has not starred directly with Kevin but has appeared in a movie with someone else having a Bacon number of 1 then that person's Bacon number becomes 2. And so on (This idea was originally set in train by the mathematician Paul Erdos who died two years ago. He was the most prolific publisher of mathematical papers this century with more than 1700 in all. If you have co-authored a paper with Erdos then your Erdos number is 1. If the best you have managed is to co-author with someone who has, in turn, co-authored with Erdos then your Erdos number is 2. And so on. Erdos's life has been chronicled in "The Man who loved only Numbers" by Paul Hoffman which has been very successful and is currently riding high in the non-fiction hardback best-seller lists).
Students at the Dept. of Computer Science at the University of Virginia have set up an online version of the Kevin Bacon game called The Oracle of Kevin Bacon (http://www.cs.virginia.edu/misc/news-bacon.html) which interrogates the online Internet Movie Database (http://www.imdb.com/). By typing in an actor's name the Bacon number is established and the chain of connection to Kevin Bacon is exhibited (with embedded links in the answer that point into IMDB, in order to reference the appropriate movies). In the pure form of the game only feature films are permitted; TV series and documentaries are excluded. Producers, Directors, Boom Operators and un-named extras don't count. It must be actors *named on the cast list on www.imdb.com*. The reason for "6 degrees" is that, until now, the Oracle counted all actors with Bacon number greater than 6 as having a Bacon number of infinity. But in recent months some intrepid investigators have found no fewer than 36 actors with Bacon number of 7 within IMDB's database of 750,000 actors ...
The School of CS at Univ. of Nottingham will go one stage further and will prepare (on our own intranet first of all!) a Frank Ramsey game. Ramsey was a brilliant mathematician (and brother of Michael Ramsey -- who was Archbishop of York and then of Canterbury in the 1950s) Ramsey theory is one of the hardest areas of Graph Theory/Combinatorics but the classic Ramsey problem is easy to understand:
"If you you host a party, what is the minimum number of guests to ensure that either there is a group of n people that know each other OR that there is a grouping of n people that do not know each other" For n=3 the answer is that you need 6 people and for n=4 the answer (I think!) is either 17 or 18 (I am in the process of checking this out with Dr D R Woodall in the School of Mathematics who is a combinatorics specialist).
The aim of the project is NOT to do advanced combinatorics for n>4 but to investigate the case n=3 in detail,using the Internet Movies Database and its pairwise co-starring relationships. Then to provide a visually appealing and informative interface to show co-starring relationships of groupings of movie actors in dinner parties of size M. The case M=5 is particularly interesting: in most cases one can set up a "successful" dinner party i.e. one can find groupings of 3 mutual `friends' or 3 mutual `strangers', described above, but there is one "unsuccesful" case where you cannot (which is why M=6 is the minimum to guarantee success). (Note: we define whether actors "know each other" at these dinner parties not in the usual social way, but solely on whether they have co-starred in movies)
By typing in an actor's name exhibit at least one "unsuccessful" dinner party of size 5 (if it exists) featuring that actor and Kevin Bacon.
This project requires *serious* thought on how to do efficient searches for graphs with the correct connectivities and on how to display and explain the answer to a non-expert Web visitor. It will also involve liaising with the people at cs.virginia.edu to build on their experience and learning a lot about Web site construction and search engine technologies.
Group mailing list: gp-mfd1.
Team members:
Project description:
The aim of this project is to develop a flexible software system for manipulation, processing and visualisation of digital images. This system will be capable of handling different image formats, handling multiple images, performing various image processing operations and providing a robust environment for interaction with and visualisation of image data. The system should utilise JAVA and web browser technologies for its design and operation.
Group mailing list: gp-mfd2.
Team members:
Project description:
VRML is an open standard for 3D multimedia and shared virtual worlds on the Internet. It's a scene description language that describes the geometry and behaviour of 3D scene or "world". Long before its official standardisation VRML became the de facto standard for sharing and publishing data between CAD, animation, and 3D modelling programs.
There are currently many VRML browsers available, but despite some powerful features many have restrictions and are not truly portable across different platforms. The purpose of this project is to design and implement a new portable VRML browser capable of harnessing the full multimedia power of the VRML format.
Group mailing list: gp-dge1.
Team members:
Project description:
Reading cursive script is a challenge that computers have yet to accomplish with sufficient success for commercial exploitation. Off-line cursive script is much harder than on-line, from a graphics, tablet, and Aunty Pauline's writing cannot be read by human beings, or at least not without great difficulty. So this project is a challenge. The project will involve scanning samples of the handwriting into TIFF files. These will then be processed to identify the outlines of the strokes, and also vectorised to produce the strokes themselves. These regions will be segmented to produce regions that are smaller than individual characters. Theses regions will then be merged using a search method known as Tabu search, and recognised using existing classifiers. So this is a difficult, probably impossible project, but the methods and much of the software will be specified for the group in detail. The existing software is in C++, but I would like much of it ported to Java as part of the project. A successful outcome would be the ability to read say 50% of neatly written cursive words from a dictionary of about 1000 possible words. If Aunty Pauline's letter is read to any extent at all then a first class mark will be deserved.
Group mailing list: gp-dge2.
Team members:
Project description:
Virginia is a mannequin doll that took a leading role in my inaugural lecture. See my web page on research for further information and a photograph. The idea of the project is simple. I would like to be able to talk to her. So there are three obvious parts to the project: speech recognition, interpretation of the speech and generation of a reply, and finally speech generation. This is of course difficult to do in a really convincing way. However I do have some software that recognises words and phrases and which can be accessed from C++ as a DLL or from Java using Sockets. I also have a version of the famous Eliza program written in Java, and a text to speech generation program. Put these three together and you have some sort of system. The problem will be in checking the input speech for being real words, and sensible grammar. I expect that much of the work of the project will go into making the speech input more reliable. The other parts are not too difficult. However it would be nice to get a good quality of speech out, and not just a monotone. There are better conversational robots than Eliza, for example a WebBot called Julia, and lesser relatives called Elmo and Colin. I don't have the sources for these. However they all work as telnet sites on the internet and could act as the intelligence for Virginia remotely. I would like the software to be written so that it is easy to "plug" a different conversational engine in place, either as a local component or as a remote telnet or socket call. The ability to have even the most mindless conversation with Virginia consisting of 3 contiguous statements will be considered a successful outcome. The project could be taken further, for example making Virginia the receptionist for the computer science Department. Making her the main phone contact point, or adding more personality to her. I cannot see this working for real, but the idea is worth studying.
Group mailing list: gp-cmg1.
Team members:
Project description:
The aim of this project is to prototype a generic event server and to demonstrate its usefulness in a range of example applications.
Events are data objects which represent something that has happened, either within the computer system or in the real world. Events can be used as a standard way of constructing loosely coupled distributed systems. Typically, components of the system generate events to represent their own actions or things which they have detected; these events are announced (in principle) to the whole system. Conversely, they can express an interest in particular kinds of events, and will be notified when these occur. Thus it is simple to add new components to the system to generate or respond to new events. Systems of this kind are particularly good at supporting some kinds of collaborative activity, or ongoing monitoring of activities or processes.
Group mailing list: gp-cmg2.
Team members:
Project description:
Synchronous multi-user activities such as tele-conferencing or on-line gaming require the simultaneous and coordinated on-line presence of a related group of users. This is called a session. Depending on the kind of application and situation, users may be invited to join the session (c.f. phoning someone up) or may take the initiative themselves (c.f. seeing an advert and buying a ticket). This project is concerned with the design and implementation of a flexible session control service, which will allow distributed users to take part in both kinds of sessions as simply and as flexibly as possible. In addition issues of security, charging and management should also be considered.
Group mailing list: gp-leon1.
Team members:
Project description:
Visitors to the new Computer Science building on the New Campus will enter the building which may have no permanent receptionionist in place. The building is quite extensive and directions as to how to get to a particular location could be presented in a number of ways. An obvious choice for a Compter Science department is to use an interactive computer based system. The object of this project is to provide such a system.
There are a number of development possibilities. For example a mouse based (non-keyboard) interaction can be used as a pre-cursor to an ultimate touch-screen final product since touch-screen technology is available that directly emulates and hence can be substitued for a mouse. A web browser interface seems to be the most obvious choiece but direct implementation is another possibilty. The screen views could be simple plans but more realistically should involve VRML models, staff photographs etc.. One essential characteristice of the system however is that is should be based on stable, well defined, easily updated data strutures that hold the relevant information on the building.
Group mailing list: gp-leon2.
Team members:
Project description: ???
Group mailing list: gp-cah1.
Team members:
Project description:
"Course Master", the Department's automatic marking system previously called Ceilidh, has been re-designed from scratch and rewritten in Java. It needs a variety of additional tools writing to enhance its abilities and performance. One of these tools is a powerful, context sensative editor that can have "modes" associated with different computer languages and indent and colour the source code of these languages in a suitable manner. It would also need to have many of the features associated with other standard editors such as "find and replace" etc. The task is to write such an editor in Java with a suitable interface for using within Ceilidh.
Group mailing list: gp-cah2.
Team members:
Project description:
Diplomacy is a board game played by two to seven players. The game is set on a map of Europe at the start of the 20th century. Each player controls one major country, and the purpose of the game to conquer at least half of Europe. In this game, unlike many, there is no luck and the only way to overpower an opponent is to have superior forces. These can only be obtained by combining forces with other countries via "diplomatic" means.
This project is to implement Diplomacy on the internet to allow (possibly) remote users to log onto the game and play it over a period of time.
Group mailing list: gp-gmh1.
Team members:
Project description:
Most programming languages are text-based, with programs being strings of characters entered using a keyboard. The aim of this project is to implement a simple programming language that is picture-based, with programs being graphical networks built by plumbing together primitive components using a mouse. There will be a fixed set of primitives, each of which corresponds to a pure function on streams of integers. The project will involve the implementation of both an editor and an interpreter for the pictorial language.
Group mailing list: gp-gmh2.
Team members:
Project description:
A micromouse is a small autonomous robot that attempts to find its way to the centre of an unknown maze as quickly as possible. The aim of this project is to design and implement a simulated micromouse that is constructed purely in software. The project will involve the implementation of three components: a maze generator, a simulator for the hardware aspects of a micromouse (at a suitable level of abstraction), and an algorithm for guiding the micromouse to the centre of a maze as quickly as possible.
Group mailing list: gp-mpj1.
Team members:
Project description:
The goal of this project is to design an interactive tool that will help its users to make up new crossword puzzles. The system is not expected to generate complete crosswords by itself, but instead should lead crossword authors through the process of laying out the puzzle, finding suitable words to fill the grid, and attaching appropriate clues to each word. Possible extensions would include adding a database of clues, providing support for non-rectangular grids, and adding save/load facilities that allow crosswords to be built up and edited over a number of sessions.
Group mailing list: gp-mpj2.
Team members:
Project description:
The goal of this project is to develop a program that will allow its users to build and view virtual 3D Lego models. The system will use a catalogue of standard brick shapes and colours from which the models will be built, and will have a `shopping list' facility that lists all of the bricks needed to build a particular model. In the real world, even young children find that Lego is very easy to use; designing a good user interface will be one of the most significant challenges in this project.
Group mailing list: gp-mark1.
Team members:
Project description:
Before the rise of the Romans the Celts dominated continental Europe. The names of regions in Europe indicate their extensive domains: from Galicia in Spain to Galatia in Turkey. Their art forms were the most advanced seen in Europe at that time, and many artists and designers today use the motifs and concepts they introduced. Yet this art did not stretch to representation of life in any of its forms: plants, animals and humans are not prominent in Celtic art. It would appear there was some religious barrier to such a representation of the work of the Gods. Rather the Celtic artist delighted in abstract patterns: cross-hatchings, spirals, interleaved lines and perhaps the most famous of all, knotwork. It has been found that the Celtic artists used certain established patterns and preset rules to generate their knotwork patterns. This project will build a system that takes the basic knotwork patterns and combines them using the various rules to create large scale works of art.
Group mailing list: gp-mark2.
Team members:
Project description:
In the construction industry a key economic activity is the calculation of the likely cost of a project: this is known as estimating. The task is usually performed as part of a competitive tendering exercise where a number of construction companies compete to provide the lowest estimated cost for a forthcoming project. While the percise techniques of estimating are varied, and in some cases considered to be secret to a particular company, the general process of tendering, submission of the estimates and adjudication have been described in a document called the `Code of Estimating Practice'. This project will create a computerised version of this code. Since the various companies involved in competitive tendering and estimating are geographically remote the system will be required to run in a distributed manner.
Group mailing list: gp-pjt1.
Team members:
Project description:
A MIME message is a textual representation of a message containing (almost) arbitrary structured multi-media information. Such a message can be sent and received via electronic mail and news. Implement the ultimative tool to read and compose MIME messages. It should faithfully and completely implement the MIME standard. It may rely on separate external programs to implement the display facilities.
Group mailing list: gp-pjt2.
Team members:
Project description:
Design and implement a system that allows you to plan a model railway interactively on the screen. The system should be parameterized with respect to a database of available tracks. It should be possible to extend the database with accessories like houses, trees, streetlamps, etc. The system should present several views on the plan, including one which allows to control the completed railway interactively. There should be support to print a shopping list of items and perhaps to maintain an inventory of items available.