Remember, this year there are two kinds of 4th year projects, COSC 480 and COSC 490. Make sure that you are enrolled for the right kind.
If you see a project that appeals to you, but the description doesn't sound as though it fits the kind of project you need to do, the staff member offering it will be happy to construct a suitable variant of the project with you.
There are several projects that involve extending a natural language processing system being built in the department. We have built a system which computes the meaning of simple sentences in English and Mäori, translates single sentences from English to Mäori and vice versa, paraphrases sentences in both languages, and engages in a simple dialogue with a user, in which the user can tell the system facts and ask it questions in both English and Mäori. The system has several components, each of which could be further extended. (Note you don't have to know any Mäori to do most of these projects!)
All of these modules can be extended, either individually, or collectively, so the list of possible projects here is fairly open-ended.
You can try the translation part of this system at http://tutoko.otago.ac.nz:8080/teKaitito/home.html if you like.
A dynamic hypertext system is a web server which instead of simply delivering stored HTML files to a user, creates web pages "on the fly", tailored to the user requesting them and the situation in which they are requested. The backbone of such a system is a text generation module, which takes as input an indication of what the user is interested in, along with a database of facts and a model of what the user already knows, and produces as output piece of natural language text, formatted in HTML. There are all kinds of applications for this technology, in particular in domains like tele-shopping. Skills which would be useful for this project include a knowledge of HTML, CGI-bins, and a bit of Lisp or Prolog. The project would focus on interface issues, and link up with a generation system being built in the department.
A bottleneck in developing a text generation system is creating the knowledge base from which texts are generated. The knowledge base must contain not only the facts which are to be generated, but also information about how these facts are to be expressed linguistically. The challenge is to allow this linguistic information to be authored by a domain expert who doesn't know about linguistics. One way this might be achieved is by letting the author enter information in some controlled form of natural language. Of course, the sentences which the author creates might contain linguistic and semantic structures the system doesn't know about---that's the whole point of an authoring tool---so the system would have to be able to draw inferences about how to encode new information syntactically and semantically, and test the validity of these inferences by asking follow-up questions or generating samples of the kinds of texts which can be generated from the new information. The project would involve implementing a prototype of such a system. I expect it would be menu-based, and implemented in something like TCL/Tk. The linguistic components would probably be in Lisp or Prolog.
An important characteristic of human cognition is that it makes use of a mechanism called "attention", that allows us to focus in on some particular aspect of the world, and quickly change this focus from one moment to the next. Attention manifests itself in all kinds of human abilities: one particularly clear case is vision. Human vision is active: we're able to fixate an object we are interested in at the centre of our retina, and track it if it moves around. Our mechanism for executing motor movements taps into this ability: for instance, a person can issue an instruction to "move your hand to the place where you're fixating (wherever that is)" and rely on active vision to maintain fixation on the object to be grasped. Instructions like this one are called "deictic" instructions, because they make implicit reference to the results of computation elsewhere in the system.
This project is to build a robot that can perform simple deictic sensorimotor tasks. The robot is able to move its fixation from one place in the world to another, to find out things about the object being fixated, and to specify motor routines relative to the place being fixated. The aim is to teach the robot how to achieve certain simple states in the world: for instance, the state where the robot has picked up a green block. The robot will be a virtual one, living in a virtual world, so we can bypass things like computer vision and sensorimotor hardware and focus on the phenomenon of deictic instructions.
We are able to use language to describe situations we see: configurations of objects in a scene, actions performed by people, and so on. Our initial representation of these situations is spatial, and some process operates on these spatial representations to turn them into sentences in natural language. What are the differences between linguistic and spatial representations? How much do they have in common? A number of researchers have recently suggested that spatial and linguistic structures have more in common than you might think: this is an extremely exciting hypothesis, which if true would open up whole new fields in linguistics and perceptual psychology. On the other hand, it might not be true. The proposed project is to review the evidence for the hypothesis, and possibly contribute to this evidence if inspiration strikes. It's a project for someone who's interested in exploring the consequences of a high-risk high-return conjecture in cognitive science.
See also projects listed jointly with Simon McCallum.
Develop a neural network toolkit in Java. This should provide the user with simple GUI tools to create, train, and test different kinds of neural network. The project will involve significant research into different kinds of neural network and tools for visualising their behaviour.
Can we create programs that help people to learn? Review the literature on Intelligent Tutoring Systems (ITS). Implement an ITS in some chosen domain (for example teaching programming, see next project).
Learning to program is hard. We have recently suggested that teachers should focus less on language knowledge, and more on programming strategies (how to use and apply knowledge, for example, how to plan, experiment, explore, and debug). Review the literature on learning to program, and explore methods of presenting and teaching programming strategies. This may involve developing an ITS (see previous project).
The Smartboard application attempts to recognise handwritten characters and morph them to a predefined character font. Currently, the recognition and morphing aspects are separate. However some recognition algorithms such as CRG (Conditional Rule Generation) establish a direct mapping between the test and training samples, allowing for more information to be used at the morphing stage. Your task will be to investigate the use of CRG and possibly other recognition algorithms for establishing this correspondence.
The free multiplatform "multimedia" Smalltalk system called Squeak has a handwriting recogniser called Genie; improvements to or a replacement of this would be welcomed by thousands of Squeakers.
A major problem with mobile robots and integrating them to be a useful part of everyday life is the problem of scene interpretation. One aspect of scene interpretation is for a robot to find an exit out of a particular environment (such as a room). This is something that humans do with little trouble, yet from purely 2D data (images) it is not a simple problem. The aim of this project is to investigate the problem and to implement proposed solutions.
A common method of object recognition is to use subgraph isomorphism to recognise objects in a scene. However, subgraph isomorphism is known to be in NP. Therefore, many suboptimal solutions have been proposed. The aim of this project is to determine how many parts should be used in suboptimal attributed subgraph isomorphism and what are the chances of success of the process.
The aim of this project is to automatically build an animated face model from a set of example images. Such a technique could be extremely useful in video telephony applications as well as general computer animation.
Research and implement a method for detecting cancer cells from a slide of cells, for example, smear tests. To be done in conjunction with someone from Medicine.
Investigate different methods for modelling cloth-like materials for computer animation
Investigate some recent algorithms for detecting and recognising faces in a video stream.
Here the idea is to cheaply recreate the action effects seen on such movies as The Matrix using a minimal amount of cameras and hardware. The particular effect I'm thinking about is having someone perform an action and then being able to look at the person performing the action from multiple viewpoints (not just the camera viewpoints).
This project will be jointly supervised by Haxby Abbott from the Department of Anatomy, and will involve the automatic or semi-automatic measurement of the instantaneous centre of rotation (ICR) for vertebrae of the lumbar spine. The project will be split into two parts. The first involves finding the ICR given two pre-segmented (pre-defined) images of the lumbar vertebrae. The second, and more interesting task, will be to automatically define the segments from the radiographs and from there calculate the ICR. This project is a practical project---Haxby has a real need for an application to do exactly these tasks, for a current clinical research project. So, if you want to do something immediately useful, perhaps this is the project for you.
Any project involving Computer Vision, Pattern Recognition or Machine Learning.
If you have some ideas about a project that don't fit in with any of the above, come and chat to me about it.
This year I shall be away for weeks 3-5; if you want to discuss a topic with me, catch me in weeks 1-2.
I am collaborating with Otago Polytechnic on the "Simon Sees" project, which aims to produce a small (Walkman-sized) device that will read text in the environment to a blind or visually impaired student. There are several projects in this area, the following are examples.
There are several OCR algorithms described in the literature. However many of them perform poorly on "real" text, that is, text that is not black on white, and perfectly horizontal.
Build a test-bed that will read in a series of images containing text and apply a variety of different algorithms to them and determine various metrics of performance. It should be very easy to test a new algorithm and compare its results to previous ones.
Most OCR algorithms (see previous project) require images containing only text or, at least, a bounding box surrounding the text to be read. My summer student has been working on this latter problem with some success. This project will entail comparing his work to the results of some recently published articles.
Many Vision algorithms work well on simple test cases but are swamped by "real-world" images that contain many objects and lots of detail. The human eye-brain system copes with this by segmenting a scene into "figures" (objects that are probably important) and "background" (the rest). Some algorithms are emerging that attempt to do the same for computer vision. Implement these algorithms, apply them to real-world images and compare their performance.
Many Computer Vision algorithms rely on "features", typically corners of what are presumed to be edges. Classical feature detectors determine corners by finding changes in contrast or intensity, which does not always work on real images. This project involves adapting these algorithms to work with texture changes rather than intensity changes.
Some other projects:
In the last century there have been many attempts to create or construct artificial languages, usually for political or idealistic reasons. The best known of these is Esperanto, but there have been many others. Chomsky's work on generative grammars and the easy availability of computers means that constructed languages can now be designed with particular attributes.
One such language is designed to be syntactically unambiguous; that is, any sentence in the language can be parsed in only one way. (Note that this is not the case for natural languages). A recogniser for the language has been built using tools such as YACC and this confirms that the grammar is indeed unambiguous. While the grammar for the language is only about one tenth the size of one for English, it is nevertheless difficult to teach since it is very different from any language that we are accustomed to.
The project will involve devising a "core" grammar of the language. This should be small enough to be specified using only a few rules, while still being rich enough to enable reasonable sentences to be constructed. Having done that you will need to develop a series of extensions that may or may not be mutually dependent.
The program should be interactive so that the user can choose different options at each stage. These choices should then determine the shape and type of the extensions produced by the program.
I am interested in having students, and would in principle be interested in other topics you might suggest.
Given a domain of objects and binary relations between them, various properties of these relations can be described. Well-known are reflexivity (for all x, Rxx), symmetry (for all x and y, Rxy implies Ryx), and transitivity for all x, y, z, Rxy and Ryz implies Rxz). One may also think of properties that express the relation between different binary relations. A simple example is "containment" (for all x and y, Rxy implies Sxy). For more examples, see [Sally Popkorn, First Steps in Modal Logic, CUP 1994]. Different relations may express things about different agents involved, in the previous example. For example, R might stand for what agent r knows, and S might represent what agent s knows, and the property expresses that s knows more than r. Interesting multiagent properties are described in [Alessio Lomuscio, Knowledge Sharing among Ideal Agents, PhD thesis, Birmingham, 1999]. There may well be a wealth of yet undescribed multiagent properties of interest to the research community. An area of interest is knowledge games [Hans van Ditmarsch, Knowledge games, PhD thesis, Groningen, 2000]. The subject of this project is to describe properties of multiagent frames, in particular game frames, and, if possible, their corresponding axioms.
In a knowledge game a number of cards are dealt to a number of players. Game actions consist of either questions and answers about cards, or announcements about winning. An example of such a game is Cluedo. Even though the question of how to model game states and game actions is fully answered [Hans van Ditmarsch, Knowledge games, PhD thesis, Groningen, 2000], it is unclear what optimal strategies are for playing knowledge games. A strategy for a player is a sequence of choices of actions for every conceivable game state that may occur. Knowledge games are games of imperfect information, where strategies are likely to be mixed (ask one of different questions with probability such and such). Game theory as such is an economic subdiscipline, for a introduction see [Ken Binmore, Fun and Games, D.C. Heath, 1992] or [Osborne and Rubinstein, A Course in Game Theory, MIT Press 1994]. For an introduction in Knowledge Games, see [Hans van Ditmarsch, Knowledge games, Bulletin of Economic Research, 249-274 Oct 2001]. Some work on this issue is also under way by Sjoerd Druiven, presently an MSc student at Groningen University, the Netherlands. Work in this area would include a substantial familiarisation with literature in game theory (microeconomics).
Lately, staff at this computer science department were bothered by the following problem: "From a pack of seven different cards, two players each draw three cards and the third player gets the remaining card. How can the players with three cards openly communicate each other all their cards without the third player learning from any of their cards who holds it?" This problem has also appeared in [Makarychev, The Importance of Being Formal, Mathematical Intelligencer 23(1), 41--42, 2001]. There are actually three solutions, see [Hans van Ditmarsch, Reflections on "the importance of being formal"] on my home page or in the departmental technical reports series. This problem can be studied in full generality, for any number of cards and players. I am currently investigating this with various other researchers. For some cards and players the communication can take place successfully, for others it cannot. The project is either to investigate what the precise constraints are, or to describe a substantial collection of concrete cases. The problem may well benefit from an implementation.
Various card games involve moves where facts (such as people holding cards) do not change but knowledge about the facts does change. As part of my PhD research I described the game of Cluedo, to which purpose I developed a generally applicable language for logical dynamics. Various other games, in particular card games, and also various other multiagent systems (such as those involving security protocols) can be described with this language. For example: the family game, memory, ... Choose a game, or multi-agent system, and provide a full logical specification, including the dynamics. The real challenge is to come up with a good example yourself of sufficient "depth": it is likely I am unaware of actually very suitable examples and games. The topic of this project is rather open and more practical than theoretical. It requires working knowledge of logical knowledge representation, as taught in the papers Artificial Intelligence and Applied Logic.
The Otago Peninsula Trust is responsible for several old guns including the famous disappearing gun at Taiaroa Head. It is not, alas, practical to demonstrate the raising and lowering of this ancient machinery because it depends for its power on energy stored from the recoil after firing. But we do have complete plans and any extra detail can be had from measuring the gun itself.
The purpose of this project is to create a 3D computer model of the gun and make an animation showing it in action. A partial model was made the year before last and we are looking for someone to complete the project.
Over the summer of 2000 we created a large-screen display that reacts to the user's eye position and hand gestures.
This project is to program an interesting and entertaining game or activity that uses this equipment. If successful, the program will be shown in public, such as at schools days or in the Otago Museum.
Orchestral conductors frequently travel with heavy excess luggage in the form of boxes of paper scores. It has been suggested that an electronic score display, built into a music stand, would save a lot of effort.
If the score displayed were editable, the computerised score could have annotations added and even notes changed. Instant scrolling to repeat and rehearsal marks would also help to make the conductor's life easier.
This project is to make a prototype to run on a laptop computer.
Filtered noise is the name given to a family of mathematical functions used to emulate a variety of natural objects and textures. Water, clouds, fire and rocks have been modelled with the aid of noise functions.
However filtered noise is expensive to calculate and there are many subtle problems associated with the use of noise to make natural looking shapes.
Investigate ways to generate filtered noise or equivalent functions and explore their application. Either discover a good cheap alternative to filtered noise, or an original way to use noise.
In 1714 Giuseppe Tartini discovered that when two musical tones are sounded together another tone could sometimes be heard. He called these additional tones "terza suoni" or third sounds and taught his violin pupils that unless they could hear them, they were playing out of tune.
Since then, the phenomenon has been studied by many musicians and physicists. In particular, the 19th century physicist Helmholtz invented a special kind of siren to help investigate these tones. The major argument among physicists has been whether the "terza suoni" had independent existence or whether they were a function of the human ear.
The really interesting thing is that the physicists have ignored Tartini's most important discovery, that the tones give an indication that the original notes are in tune. I have good reason to believe that the tones produced by Helmholtz are subtly different from the Tartini tones associated with resonant strings or pipes and this is why they occur only for certain notes. Helmholtz's tones are simply differences of frequencies from two non-resonant sources.
Using a computer, we can create the same sound as a string or pipe, but from a speaker that has no particular natural resonant tone. Thus we can reproduce the essential feature of Helmholtz's siren without restricting the tone colour. We can also use Fourier analysis on the computer to detect the tones independently of a human listener.
Develop the necessary computer programs and conduct the physical experiments needed to settle these questions.
Studying musical form often requires a lot of tedious analysis of chords, rhythms and melodic elements. But computers can provide systematic ways to classify, count, and recognise these elements. The idea of this project is to provide a collection of tools for helping with these routine tasks. Find a useful area of this work and create a suitable computer aid.
In 2000, software was developed here to tell a musician which note is being sung or played and how accurately in tune it is. The program, however is not really accurate enough and the interface needs some development.
Discover why and improve this program to make it useful to practising musicians.
Textures in computer graphics are used to add detail cheaply to models. Some kinds of texture are well understood: wood grain and marble for example.
Others, particularly the patterns created by irregular formations of similar objects like bubbles and gravel, have never been simulated effectively. Study this problem, find some new texture to model, or improve on an existing model.
Auto-stereograms are pictures that can be viewed as 3D or 2D images. They depend, for this effect, on an implicit knowledge of the 3D structure of objects portrayed. Mostly they are used to represent stylised objects that have been created as 3D computer models. But all the information needed to create an auto-stereogram is inherently contained in a stereo pair of photographs of any natural scene.
This project is to devise software or a process to make auto-stereograms from stereo pairs.
In 1999, after five summer vacation's work, our department finished the 3.5 minute, computer-animated movie "Dragon Gate". Since then, we have made only tiny movie segments. If we can put together a team of four COSC490 students, we can make another movie during the year as a group project. If you think you might be interested in this project, e-mail me and I will arrange a meeting of interested parties. This can only succeed as a group project. It is far too much work for an individual.
Simple networks of data structures can be used to reorder an input stream to an output stream. Our efforts to understand the possible effects of such networks are hampered by not being able to conduct practical experiments except on a very small scale. The project is to develop a GUI which will allow the user to specify the layout of such a network using standard components (stacks, priority queues, registers), and then observe its behaviour either under a set of specific commands, or in a random mode.
An XML document is basically a tree, and a DTD is a grammar for these trees. The sequence of children an element may have is constrained by a regular expression. It is useful to construct DTDs by example, especially for compression.
Several methods have been described in the literature, and I have an unpublished one. A critical review of several of these methods would make a good COSC480 project; experimental comparisons would complete a COSC490 project.
XPath is a query language for XML. It is a notation for selecting a set of nodes in a structured document. Unfortunately, the specification is not as clear as it could be, and it seems to be missing a number of important features.
The goal here is to develop a clear formal specification of XPath, test it with publically available test cases, and find some transformation property that might be useful for query optimisation and either show that it is valid or show that it is not.
I have a design for a clean simple XML Query Language called XTrack.
It is based on regular expressions. I'd like an implementation of it in
C, and some performance comparisons with libxslt.
Alternatively, a good analysis of the relative strengths and weaknesses
of XTrack and XSL (or some other XML query language) would be useful.
At the moment, the easiest way to extract information from an XML document is to write a program which processes the document according to the tags it sees. Several attempts have been made at ad hoc XML query languages (XML-QL, LORE, XQL and XSL); these languages are big and hard to "get a grasp of". In this project you will design a small language for querying and transforming XML documents and provide a simple implementation for it.
Cascading Style Sheets are the notation that HTML 4 uses for controlling the appearance of web pages. Basically, a CSS rule specifies a context and a bundle of attribute-value pairs.
The CSS1 and CSS2 specifications from the World-Wide Web Consortium explain CSS in rather fuzzy English; the book by the inventors (which is in the Science library) is no better.
The task of this project is to develop a formal specification that says precisely which attribute-value pairs are to be associated with each node in the parse tree of an HTML or XML document by any given CSS sheet.
Ideally the specification would be tested by converting it into executable form, say as Haskell or Mercury, but that is not a requirement.
AWK is a UNIX programming language for manipulating files that can be viewed as sequences of lines. I've done some SGML manipulation in AWK, and from that have designed an AWK-like language with direct support for SGML. I also have an unfinished compiler for this language, in Prolog, about 3,600 SLOC.
There are at least two possible projects here:
Project Gutenberg is an ambitious project whose aim is to provide as much as possible of the world's literature in free electronic form. Volunteers produce plain-text versions of out-of-copyright works, upload them, and the rest is a free reading frenzy.
Currently they have about 2GB of text on offer. Most of this is English, because that's what they've been given. Some texts are in other languages.
Plain texts such as books are not marked up. Yet they have structure. Your mission, should you choose to accept it, is to devise an SGML or XML "grammar" for books (I will provide lots of help with that), and a method of converting plain text Project Gutenberg books to this format that works with at least 3 books. Python or Perl might be suitable languages for writing the converter in, but that's up to you.
Recovering structure from existing semi-structured or even unstructured documents is a real task for many organisations.
ASCII is a 7-bit character set, with 95 printing characters. ISO Latin 1 is an 8-bit character set, with 191 printing characters. Unicode (which is for all practical purposes identical to ISO 10646) is a 31-bit code in which there are currently more than 58,000 printing characters.
For a variety of reasons (mainly humanity's creativity at inventing scripts and boneheadedness at developing standards) Unicode is quite complex to process. There are several useful, feasible, but challenging sub-projects:
I would be particularly pleased to see Indonesian to English or Mäori to English done. The project mainly involves working out a semantic representation for the meanings of words in the source language (using appropriate type hierarchies and so on) and an efficient way of storing the word to meaning mapping using Prolog or a deductive data base language. You need not be fluent in both the source and target language. I have some books I can lend you which will give you a place to start.
This topic can be handled at two levels. As a project, it is basically an exercise in knowledge representation. You can test it out by using your dictionary to do information retrieval with the documents in the source language and the queries in the target language (this is why it is important that the word to meaning mapping should be efficient). As a thesis, you can take it as far as you like.
For this topic it would be a big help to know Prolog simply because it makes this kind of thing so much easier, but Haskell or ML would be good too.
Write a morphological analyser for a non-European language. Previous theses (for Indonesian and Persian) will be available to see how it's done. There is a free tool called PC-KIMMO that makes it a lot easier to do this, but you may use any tools you choose.
A morphological analyser is a program which can break a word like "unavoidably" into meaningful pieces like UN+AVOID+ABLE+LY. Such components are useful in computational linguistics and information retrieval. You need not be a native speaker of the language you choose to study, nor even especially fluent. All the information you require is in books.
A particular challenge for Mäori is the three different orthographies in use (differing in whether/how they indicate vowel length); can you use context to recover vowel length?
The following projects may be done in any non-European language, such as Tongan, Samoan, or Indonesian. Mäori would be preferred, but the main criterion is that you should be or should have access to a fluent speaker of the language of your choice, which we will call X.
Information retrieval systems for English basically work by
This project involves
The first task for this project will be to find out what has already been tried for X.
Whenever you use a search engine on the Web, you are doing information retrieval. HTML 4 provides a way to tag (parts of documents) with the language they are written in, so that appropriate conventions may be used. Your ideas could end up in a search engine.
Hidden Markov Modelling is a machine learning technique that learns an approximate grammar for a language by fitting a finite state automaton with random transitions. We have software that uses this technique to tag unrestricted English text with the part of speech of each word, including words it has never seen before. This project involves applying that technique to the non-English language of your choice, and evaluating how well the technique works. This requires access to someone who knows the language you choose.
A related topic would be seeing whether this approach lets you recover vowel length from a Mäori text that doesn't distinguish it.
A part of speech tagger is a program that takes a text and labels (tags) each word with its part of speech (is it a singular noun, a plural noun, an article, a preposition, a transitive verb, and intransitive verb, etc). The really clever thing about such programs is that they use statistical information about a language and about how its words are put together to make good guesses about words they have never seen before.
There are quite a few papers about these programs, which generally use a technique called "Hidden Markov Models", which have a lot of other applications as well; some of them use "N-grams", which idea is used in text compression.
Extend autopun to make bilingual puns involving X. There is a program called "autopun" which converts English text to phonemes (unfortunately with an American accent) and then parses the sequence of phonemes trying to find other sequences of words that sound the same. The classic example is "It's hard to recognise speech" coming out as "it's hard to wreck a nice beach" which is unfortunately untrue. The source code for autopun is available. This project involves converting X words to phonemes (you will almost certainly have to extend the set of phonemes that autopun knows about) and converting phonemes back to X words.
This should be fun, but has a serious purpose.
The Cook Strait ferry currently takes the most direct path from Wellington to Picton and back. It is not optimised for wind, rain, weather, tides, and so on. The project is to find a way for a computer to find an optimal (or at any rate better) path. Criteria might include travel time, fuel consumption, or profit. We have a contact at Tranz Rail who can provide information and is interested in seeing this happen.
It sometimes seems as though Otago's most prolific crop is gorse, and I sometimes wonder what we might export from it. Another interesting question is whether we can find patches of gorse infestation from satellite or aerial photographs. Can we tell gorse from broom (they both have yellow flowers)?
The Marine Science group were interested in tracking the growth of sea cucumbers. Like many marine organisms, sea cucumbers are basically generalised cylinders. They have patterns on their skin, and the goal is to write a program that can recognise individual sea cucumbers from their pictures, despite changes in scale, orientation, and posture. Marine Science aren't working on this actively any more, but they have a lot of pictures and are able to explain the problem.
Sea anemones are basically generalised cylinders. They have genetically controlled patterns on their skin. All the anemones in a clone have the same pattern; anemones from different clones have different patterns. The Marine Science group would like to be able to tell from pictures whether two anemones belong to the same clone; this is part of an active project.
Copilia is a pinhead-sized marine crustacean whose females have very unusual eyes: each eye has a single photoreceptor which is mechanically scanned. The project is to construct a neural net model of this eye system and conduct computational experiments to study whether the scanning is actually a useful improvement for mate-finding or whether it has some other virtue.
Modify ispell or any other spelling checker of your
choice to check the spelling of comments in source code. You may choose
the programming language, although C, C++, Java, Smalltalk, Prolog, or
Erlang would be preferred. Better still, try to come up with a design
that makes it
easy to plug in support for other programming languages, though you still
need only implement checking for one.
The very best thing would be to recognise identifiers defined in the language standard and declared in the source code as "words" and not report them as errors, but that requires a two-pass algorithm. (Why two passes? Because comments often describe the next declaration.) However, even just checking the commentary as if the source code proper were absent would be very useful.
If the spelling checker you modify is not interactive (and
ispell is), take care to produce output in error(1)
format so that UNIX tools such as emacs can be used.
Try running your modified spelling checker over an existing body of code. In your report, comment on the practical utility of this tool.
Note: it took me about an hour of reading the ispell
sources to find the one small place that needed to be changed. However,
ispell is a large program, so you may find it harder than I
did. You don't have to use ispell, but you do have
to report somehow where the errors are, so spell(1) won't quite
do.
This is a software maintenance project and might suit COSC 480.
If you've ever done any statistics, you'll know about t-tests, chi square, regression, analysis of variance, and so on. According to [Rand R. Wilcox, Fundamentals of Modern Statistical Methods, Springer-Verlag 2001], those techniques are not only 40 years out of date, they are dangerously vulnerable to the quirks of real-life data sets.
We have source code for two free statistics packages, XLispStat and R. Implement some of the techniques described in that book in clear well-documented code for either or both of these packages, or any other robust methods.
Sets are important data structures. We would like to have space-efficient representations for them with time-efficient algorithms for performing the basic set operations union, intersection, relative complement, membership, and enumeration of elements, and we'd like to have them for declarative programming languages.
I have six set representations that I would like implemented and benchmarked, or analysed. Two are already implemented in Prolog and Lisp. There are also some interesting data structures in Okasaki's book. This project involves
In 1999, a student wrote a simple Entity-Relationship drawing tool for me, using TCL/Tk. What I wanted was a tool that could be used to draw full Enhanced E-R diagrams as described in chapter 21 of Fundamentals of Database Systems, by Elmasri & Navathe.
The current program doesn't handle everything, and there are some user interface problems, some of which may require small fixes, and some of which may require partial redesign. For example, if there is an object on the screen (an entity or relationship) and it is moved, other things (its attributes and lines connecting it to other objects) should move too. At the moment they don't. It would also be nice to have some semantic checks, and the ability to generate SQL.
For this project, you need to know or learn TCL/Tk. I can lend you a book if necessary. Tk is the platform-independent GUI kit; it has been "borrowed" by Perl, Ada, Scheme, O'CAML, and others. I find Tk a lot easier to use than AWT. It's very useful to know. The project also relates to user interface design, and above all to maintenance.
The best software tools in the world are no use unless people who would benefit from them are told clearly how to use the tools to solve their problems. A good technical writer is one of the most valuable people in a programming team (if you can't explain it, it's probably wrong).
There is a static checker for C called LCLint. If you just give it
your C source files, it can find most of the things that lint(1)
can. If you give it additional specifications, it can check a lot more for
you. However, the existing documentation takes it for granted that you
already understand a lot of this, or have the patience to read a couple of
books.
A user manual, which started with what LCLint can do for you with no extra specifications, and introduced each additional thing you can do, with examples, would make this tool much more accessible. I envisage a document somewhere between 60 and 120 pages. Perhaps half the bulk of the text would be examples. The document should be written using LaTeX, and should have an excellent index and table of contents. I will be able to answer most questions about the program, and we have a good e-mail relationship with the maintainer of the program.
There is a free C compiler called lcc. The source code
has been published and explained in a book, which I can lend you. It
handles all of C89, but since then, several extensions have been added,
and there is now a C99 standard.
Pick a small number of new features, such as
implement some of them (you won't have time to do as many as you think),
and test them. Write up what you have done and what you have learned.
Send the lot to the lcc repository.
I find pretty much everything interesting, so if there's a project you would like to do that is not in my list, ask me.
Numerous projects can be done under facial animation and modelling, including facial expression generation, hair modelling and rendering, skin modelling and rendering, wrinkle generation, prosody, syllable-based generation, song, GUIs, and a literature survey.
This work could fit in with or expand current research or start in an entirely new direction.
In ray tracing, the ray is cast backward from the eye toward the scene. When the rays hit objects the lighting is solved. In photon tracing, the photons are traced from the light source to a diffuse surface. Much more realistic scenes can be generated. This project would involve implementing a photon tracer or a photon mapper and then possibly modifying to try new techniques.
In the 1960's it was OK to illuminate a human subject with an X-ray source and capture the subject speaking with motion pictures. These cineradiographic films allow the internal workings of the vocal track to be seen during speech. This project would involve writing computer vision software to detect and track the vocal tract parts during the films.
Wouldn't it be nice to be able to get a 3D relief map of Dunedin (and other New Zealand cities) that showed the heights of roads? As well, what if we took satellite images and added them to the 3D terrain and road data and allowed interactive access to the data. Maybe add things like path planning, what is the best way to get from my current location to a grocery store. The best route could minimise distance travelled, or some other function which took into account travel time by foot, such as avoiding steep hills.
This project should be done by a small group and that group should be made up of programmers and people with artistic talent. The aim of the project would be to produce a film short using computer technology.
Study and implement three dimensional graphics techniques. Some possibilities include: physically-based modeling, flocking, deformable quadrics, FFDs, and so on.
It might be fun to build this in Squeak, the free multimedia Smalltalk, as it already has a 3D animation kit.
I have motion capture data of speech that needs to be processed. This would involve writing software, possibly in Matlab or some suitable language, that takes the data and removes the rigid-motion of the head (that due to the bending of the neck) leaving just the non-rigid motion of the face as well as the motion from the movement of the jaw. The movement would them be mapped into a set of parameters that describe the motion of the lips and the jaw and statistically analysed.
If you have some area in computer graphics, speech, sound, vision that you would like to learn more about or you have some neat idea you would like to implement, see me and we can discuss it.
Investigate the evolution of co-operation in an embedded system. Using the 10 Lego robots that the department owns, research and implement a theory of co-operation among simple agents. This will involve the use of a Lego simulator in Java and the NQC language for Lego.
Using either Theseus or Orc investigate different navigation theories including grid-based searching and path planning. The robot used will depend on the direction of the research undertaken.
There is a large amount of feedback in the early visual systems of most animals. Very little is known about the function of this feedback. Research the different opinions about the purpose of this feedback and implement either a simple neural network with feedback for visual tasks and/or edge detection/feature extraction using feedback in a manner consistent with feedback in the visual cortex.
Robots are fun. They combine a range of theoretical challenges with the very practical requirements of making the thing work. Robots also provide a way to explore the core philosophical issue at the heart of artificial intelligence today: does true intelligence have to be "embodied" or "situated" in a body and an environment? The department has a range of robots, including two large mobile ones (one "home made" using the QNX real time operating system and prototype vision software, one commercial system using multiple sonar sensors). If you have an interest in a robotics topic come and discuss what you want to do and we will see if it can be turned into a 490 project.
Most neural networks are plagued by a problem often called "catastrophic forgetting"---newly learned material overwrites / destroys any old information in the network. This is a limitation in practical terms, and a serious problem for cognitive modeling (people learn new stuff all the time without forgetting everything they used to know!). Review the literature on this problem, including our pseudorehearsal method and its links with consolidation of learning in humans during sleep. Develop and explore extensions of these ideas such as how excessive rehearsal of pseudo-items affects memories, how pseudo-items are generated in Hebbian based back-propagation networks, distinguishing real memories from spurious memories, and many more.
Neural networks are computational methods inspired by the brain that use networks of simple interconnected units as a basis for implementing memory and processing systems. Genetic algorithms are computational methods inspired by evolution that solve problems by "breeding" a good solution from "populations" of possible solutions. Artificial life is a framework for studying "emergent" computation by simulating systems of simple entities that interact in a "life-like" way. Projects can be offered in any of these areas if you have an interest that you would like to develop. Projects would include a literature review and implementing a working system.
A racing cyclist on a track requires precise feedback about the pace at which he or she is travelling. This is useful information to guide the cyclist's efforts during training sessions. Due to the nature of a bike track, it is not convenient for cyclists to take their own times. Normally a coach provides timing information and communicates it verbally to the rider.
This project aims to design and construct an automatic system that can monitor the progress of a rider on a bike track, provide pace information and compare against a predefined schedule to provide feedback to the rider on the track directly. This project will combine software and hardware design and may result in the construction of an embedded system using custom electronics.
Computers that play the game of Scrabble have in recent years begun to approach and occasionally surpass the skill level of the best human players. The novel component of computer game play that has added most capability is the evaluation of the outcome of a prospective move by simulation. Typically, a program will use a Monte Carlo simulation to estimate the outcome by simulating several randomly-selected moves, although there are other potentially-viable methods. The evaluation of the outcome is made more subtle by the need to consider factors such as the letters remaining on the rack after the play and the board position as well as the score achieved.
This project will investigate several simulation methods and provide a comparative study to indicate the suitability of each for inclusion in a program that would provide a strong computer opponent.
Taking a simple system, for example a binary adder, devise an algorithm to implement diagnostic reasoning. Before one does this, of course, you need to have a firm idea of what diagnostic reasoning might involve. How does one know that diagnosis is called for in the first place? What does one hope to achieve in the end?
The emphasis is on conceptual foundations rather than on efficiency of the implementation, and the approach will be that of Raymond Reiter's model-based diagnosis.
Temporal logics have been applied in such diverse fields as AI and concurrency. There are many different ways in which a temporal dimension can be added to reasoning. Some of the differences have to do with the structure attributed to time---in the simplest case, we may visualise a single straight line of successive instants, but other approaches allow the line to branch into many futures, and yet others allow branching into the past also.
This project would involve making a survey of the various approaches and should produce a description of what the basic elements are that we may vary in order to change from one temporal logic to another. The project is theoretical rather than implementation-oriented. Its primary purpose is to assist the student to acquire a comprehensive overview of temporal semantics, and so no prior knowledge of logic is required. With luck the project will suggest directions for future research at MSc or PhD level.
This is suitable for COSC480, as it is essentially a literature study.
Computability is usually studied in the context of the natural numbers 0, 1, 2, ... Turing machines can be conveniently encoded as natural numbers, partial recursive functions are defined on the set of natural numbers, and so on.
Can we do something analogous for the real numbers? The computable objects won't be the same as in classical computability theory, but it would be interesting to see whether some intuitive sense of "effectively computable" can be preserved.
Part of the project is about deciding on a suitable approach---should we use machines or "recursive" functions or some ideal programming language? Understanding the papers of Jeff Zucker and John Tucker would be an important goal.
The package java.net in the Java class library provides a high-level application programmer interface for socket-style network programming. Previous student research has created an extension of the java.net classes that allow the same interface to be used for communications across an Asynchronous Transfer Mode (ATM) network based on native ATM protocols (instead of using less efficient ATM network facilities such as LAN emulation). This software is written mostly in Java, but contains native method calls that invoke functions in a Windows dynamic link library containing driver software for a particular brand of ATM and network interface card (NIC).
The task of this project is to port the above package to Linux with the ForeRunnerLE ATM NIC and extend the current Java networking API to support the declaration of Quality of Service (QoS) requirements for ATM network connections.
A Distributed Shared Memory ( DSM) system can provide application programmers the illusion of shared memory on a network of workstations. It facilitates the task of parallel programming in distributed systems. The tasks of this project are to investigate and implement various applications on DSM systems and to evaluate their performance on various DSM systems. Work will be carried out on an ATM network. C will be required.