CLASSIFICATION: Simulation SH: Y - C CM: Y - C BM: Y - C
Project: 000 Supervisor: PJJ
I have always been interested in the way in which human communities and economies develop, originally because I wanted to create imaginary countries to fight wargames in, but nowadays as a way of understanding history. In the past few years, simulations by social scientists, economists, archeologists and historians have progressed to the point where this almost seems a feasible, but long-term goal. This aim of this project is to investigate what has already been done, and then pick an interesting and relevant (i.e. computer-science) aspect of this work to follow up. Remember that this is only a third year project, and it is quite reasonable to reimplement an existing piece of work in a better way, e.g. in Java to make it more easily available.
REFERENCES:
The easiest starting points are articles from:
New Scientist 4th October 1997:
http://www.newscientist.co.uk/ns/971004/features.html
Discovery Channel:
http://www.discovery.com/area/science/life/digitalplayroom.html
Science News:
http://www.sciencenews.org/sn_arch/11_23_96/bob1.htm
Here are some more detailed references:
CLASSIFICATION: Simulation SH: Y - F CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
CS1011 makes use of a simulator for a very simple computer, MU0. The simulator can run both individual assembly-code instructions and at the level of the sequence of clock cycles used to implement such instructions. However, this computer is also used by CS1211, but the implementation is rather different. This project is about re-implementing the simulator in Java, and updating the detailed simulation of the hardware. My hope would be that some flexibility would be built into the new system, so that it would be easy to modify if the detailed hardware changed again.
EQUIPMENT: Java
more ideas for projects
CLASSIFICATION: Language Processing SH: Y - LF CM: Y - LF BM: Y - LF
Project: 000 Supervisor: PJJ
CS2121 uses lex and yacc in most of the lab exercises. However, these tools are specifically designed to be compatible with C, and we are changing from teaching C to teaching Java over the next few years. There are several alternatives to lex and yacc that are compatible with Java - some are direct replacements, some are very different but with similar functionality. The aim of this project is investigate these various alternatives, and in particular to redo the various examples and exercises. The ultimate objective is to decide which of the available tools should be used in a future version of CS2121. It may be that more than one such tool is picked, as there are examples of several different classes of parser-generators available (e.g. bottom-up, like yacc, or top-down), and CS2121 could discuss their relative merits.
An obvious extension of this project would be to use the chosen tool to solve a bigger problem. One possibility would be to re-implement one of the programs I use to process student or exam information, currently written in C.
REFERENCES:
CS2121:
http://www.cs.man.ac.uk/~pjj/cs2121/index.html
some alternative tools are listed at:
http://www.first.gmd.de/cogent/catalog/java.html
COURSE PREREQUISITES:
CS2121 (or perhaps CS3041) would be a big help, but is not necessary
more ideas for projects
CLASSIFICATION: Language Processing SH: Y - UF CM: Y - C BM: Y - C
Project: 000 Supervisor: PJJ
The Java Compiler Compiler (JavaCC) is a parser generator created by Sun for use with their Java language. It is roughly equivalent to tools like Lex and Yacc, but has different underlying mechanisms. This makes it easier for humans to understand what it is doing, but also makes the basic system less powerful. Because of this, users have to put some effort into modifying an initial grammar to make it acceptable to JavaCC.
For example, we would normally recognise non-associative, left-associative and right-associative operators using non-recursive, left-recursive and right-recursive grammars respectively:
non_expression = sub_exp | sub_exp '=' sub_exp left_expression = sub_exp | left_expression '+' sub_exp right_expression = sub_exp | sub_exp '^' right_expressionHowever, with JavaCC, we have to rewrite the grammars:
non_expression = sub_exp ( '=' sub_exp )? left_expression = sub_exp ( '+' sub_exp )* right_expression = sub_exp ( '^' right_expression )?(We have had to left-factor non_expression and right_expression, and convert left recursion to iteration for left_expression.)
This project is about producing a program that helps users to modify their grammars, to get the most out of JavaCC. The program would be interactive, so that it could point out problem areas, make suggestions, and allow the user to pick a suitable modification. Some specific areas that could be investigated are converting left recursion to iteration, left-factoring and look-ahead and error handling.
There are several possible extensions to this project if time permits, implementing other similar transformations on grammars, such as removing empty, trivial, or unusable grammar rules.
I would expect the program to be written using Java and JavaCC.
REFERENCES:
JavaCC is now maintained by WebGain
http://www.webgain.com/products/metamata/java_doc.html
A similar, but not identical, tool:
http://www.iit.edu/~tc/llk.htm
COURSE PREREQUISITES:
CS2121 (or perhaps CS3041) would be a big help, but is not necessary
more ideas for projects
CLASSIFICATION: Language Processing SH: Y - C CM: Y - C BM: Y - C
Project: 000 Supervisor: PJJ
Rainbow, LARD and Balsa are all languages used for designing asynchronous hardware in this department. To make the tools associated with each language available to all users, we would like to have translators that can convert between these languages. (Although these languages are used for hardware design, and Rainbow is designed for use with formal methods, neither of these aspects should significantly affect this project.) We would like the translator to be written in Java, using the available parser-generator tools (similar to lex and yacc).
The Rainbow language has several simple component sub-languages (Yellow, Green and Table), that can be used to describe different kinds of actions in different styles. It will be sensible to start by dealing with just one of these. Because of the intrinsic difficulties of translating between high-level languages, we really only expect a 95% translation, with the most difficult aspects being reported to the user for intelligent action.
There are several different possibilities, including:
We have a Rainbow compiler written in Java, that parses a Rainbow program to create parse-trees, checks them to deal with declarations and types, and then outputs "code" for the simulator. This project essentially consists of adding methods to each class used in the parse-trees, that will output the target HDL instead of simulator code. There are various possible target HDLs, including VHDL, Promela and Balsa.
A previous 3rd year project implemented a translator from Balsa to Rainbow, using JavaCC and Java. The output from this can then be used as the input to a Rainbow compiler (also written using JavaCC and Java) so we can run it on the Rainbow simulator. This project consists of integrating these two steps into one - i.e. modifying the Balsa translator to create the parse-trees that are currently created indirectly by the Rainbow compiler. It should then be possible to use the facilities of the Rainbow compiler to improve the translation of the Balsa.
The sub-languages of Rainbow (Yellow, Green and Table) can be used to describe different kinds of actions in different styles. It is expected that these different components will be used at different stages of the design. Typically, a design will start out in Yellow, which is similar to common programming languages. It will then be transformed into Green, which is closer to the real hardware, so that the user can modify any newly-visible details. For example, a variable in Yellow becomes a register in Green, and the user can then adjust the connections to the hardware devices that set or use its value.
Currently, a user has to convert Yellow to Green by hand. We want to provide automatic translations from Yellow to Green. We have a Rainbow compiler written in Java, that parses a Rainbow program to create parse-trees, checks them to deal with declarations and types, and then outputs "code" for the simulator. This project essentially consists of adding methods to each class used in the parse-trees for Yellow, that will output Green instead of simulator code.
REFERENCES:
Rainbow:
http://www.cs.man.ac.uk/fmethods/projects/AHV-PROJECT/ahv-project.html
VHDL:
http://vhdl.org/vi/comp.lang.vhdl
Promela:
http://netlib.bell-labs.com/netlib/spin/whatispin.html
Balsa:
http://www.cs.man.ac.uk/amulet/publications/thesis/bardsley98_mphil.html
LARD:
http://www.cs.man.ac.uk/amulet/projects/lard/
COURSE PREREQUISITES:
CS2121 (or perhaps CS3041) would be a big help, but is not
absolutely necessary
EQUIPMENT: Java
more ideas for projects
CLASSIFICATION: Language Processing SH: Y - LF CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
This project consists of implementing an interpreter for the text-processing language TRAC. As an example of TRAC, the following:
#(ds,factorial,(#(eq,x,1,1,(#(ml,x,#(cl,factorial,#(su,x,1)))))))' #(ss,factorial,x)'defines the equivalent of a function, factorial, with one parameter, and:
#(cl,factorial,5)'invokes it to calculate 5!.
Initially you will concentrate on implementing the kernel of the interpreter, subsequently progressing to implementing some of the other primitive operations, or maybe even designing your own. You will have to write significant test programs in TRAC at all stages of the work. Alternatively, once you have implemented sufficient of TRAC, you could concentrate on writing a significant program in TRAC itself, such as a text processor.
REFERENCES:
A short introduction to TRAC:
http://www.cs.man.ac.uk/~pjj/projects/trac_doc
TRAC Language:
http://www.tracfoundation.org/
more ideas for projects
CLASSIFICATION: Language Processing SH: Y - LF CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
Threaded code is a technique for implementing interpreters for computer languages, and is especially suitable for reverse-polish notation. (It has nothing to do with using "threads" to get the effect of multiple processes running in parallel.) This project consists of designing and implementing a threaded code language and system based on the paper reference, available from me.
Initially you can implement any sensible subset of 'Generalisations' 1 to 11 and any 'Advanced Concepts', including those from the bibliography, such as 'defining words'. It would be reasonable to aim initially at about generalisation 8 but to design your program to be easily extended. You will have to select your own set of primitive commands, including integer arithmetic and input-output. You should expect to enhance your language by implement new facilities such as virtual memory, filestore, parallelism, data structures, or any other features to be found in computer languages.
REFERENCES:
What is threaded code:
http://www.complang.tuwien.ac.at/forth/threaded-code.html
Kogge P.M.
An Architectural Trail to Threaded-Code Systems
IEEE computer March 1982 pp22-31
more ideas for projects
CLASSIFICATION: Information Systems SH: Y - F CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
Although the University Central Timetabling Unit has control of our 4 largest lecture theatres, we still control the rest of the rooms in this building. As such, we make them available to any staff and students to book for meetings. Currently, the booking system is a sheet of paper for each room for each week of the year, that has to be signed by the person booking the room. This project is about transferring this paper system to a web-based system, allowing the status of rooms to be checked and rooms to be booked much more easily.
An initial implementation could be very simple, but if time allowed we ought to consider other facilities and features. For example, how do we ensure that only "sensible" bookings are made, particularly if we allow access to the whole uiversity? How can we safely allow people to cancel bookings that are no longer needed? Could we add a feature to alert users if a booking was cancelled in some range of rooms over some range of times or days?
REFERENCES:
Next year's room timetables
http://www.cs.man.ac.uk/Intranet_subweb/timetable/0102/R/index.html
more ideas for projects
CLASSIFICATION: Information Systems SH: Y - LF CM: Y - F BM: Y - LF
Project: 000 Supervisor: PJJ
We spend a lot of time assessing students, and we put a lot of effort into ensuring that this process is fair and error-free, but we have done little to assess the usefulness of the results of this assessment. Some of the questions that need to be answered before we can really understand how well we are assessing students are:
This project would start by creating a prototype system by "glueing" together various Unix tools (e.g. gnuplot) and simple programs written specially (e.g. to calculate means and standard deviations) to investigate the characteristics of real sets of (anonymised) marks. As a minimum, we need to be able to read sets of exam marks, plot them (e.g. frequency or cumulative frequency graph) and calculate some simple statistics for an individual exam (e.g. mean and standard deviation) or for pairs of exams (e.g. correlation).
Once we have an understanding of the basic information in the data, we can then procede in various ways: with more detailed analysis, or automatic scaling, or to investigate the correlation between A-level and university results or between one year's results and the next.
REFERENCES:
see
http://www.cs.man.ac.uk/~pjj/projects/fairexam
and
http://www.cs.man.ac.uk/~pjj/projects/examrefs
[added later -
http://www.satac.edu.au/Scaling2000.pdf
http://www.math.auckland.ac.nz/~mcintyre/Papers/wbeps.html
http://www.shef.ac.uk/~ms/staff/biggins/msp-www.html
]
COURSE PREREQUISITES:
some knowledge of statistics would be a help, but is not essential.
EQUIPMENT: Linux
more ideas for projects
CLASSIFICATION: Human Computer Interface SH: Y - F CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
Timetabling for this department is currently performed with the minimum of computer assistance, only capable of detecting problems in the timetable I create, rather than creating it for me. GATT is a general-purpose program for generating timetables, developed at Edinburgh University. I would like to use GATT to automatically create the timetables for this department. However, because it is general-purpose, GATT has a very simple-minded control language, and it requires some very verbose problem-description files.
This project has two main objectives:
REFERENCES:
GATT:
ftp://ftp.dai.ed.ac.uk/pub/gatt/ and
http://www.dcs.napier.ac.uk/~emmah/software.htm
more ideas for projects
CLASSIFICATION: General Applications SH: Y - F CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
Timetabling for this department is very difficult and currently performed with the minimum of computer assistance. The major difficulty seems to be that it is only just possible to satisfy some of the constraints - e.g. the number of hours of lectures that must be in 1.1 is only slightly less than the number of hours in the week that it can be used. However, because of this, I have found that a heuristic for creating the timetable is to identify these constraints, pick the tightest, and resolve it before proceeding to the next tightest constraint. In practice, the major constraints on our departmental timetable seem to be:
The aim of this project is to produce a system that inputs information about the constraints on rooms and student availability, and outputs details about how tight each of them is, both alone and in combination, so that I can determine the order in which I should deal with them.
REFERENCES: delete if none.
COURSE PREREQUISITES: delete if none.
EQUIPMENT: delete if none.
more ideas for projects
CLASSIFICATION: Graphical Systems and Applications SH: Y - F CM: Y - F BM: Y - F
Project: 000 Supervisor: PJJ
Rainbow is a language created in this department for designing asynchronous hardware. Rainbow designs look like ordinary programs, that describe the actions to be performed on the values flowing through the hardware. The Rainbow language has several component sub-languages (Yellow, Green and Table), that can be used to describe different kinds of actions in different styles.
One style that Rainbow does not directly include, but that hardware designers use, is State Machines (sometimes called Finite State Automata or FSA) and we would like to make some provision for it. This project has two main parts: creating a graphical system that designers can use to draw various kinds of state machines, and generating simple versions of these machines in Rainbow. For each part there are various options, so a simple version of the project would just explore one possibility, whereas a more complex version might provide more alternatives:
Should the FSA be deterministic or non-deterministic, and should the outputs be determined by the transitions or the states? In fact these are all equivalent, so what we are really looking for is convenience for users and simplicity of translation.
Should we generate Green or Table or Yellow? Green has a graphical form, which superficially looks very similar to state machine diagrams, so it may be easier for the user to relate to, or it may turn out to be very confusing. Table and Yellow are both textual, like normal programming languages, and either could be useable. Table, as its name suggests, is tabular, and seems well suited to the problem. Yellow is more like a conventional programming language, and may therefore be more understandable to a user.
For compatibility with the rest of the Rainbow system, I would expect this project to be implemented using Java.
REFERENCES:
Rainbow:
http://www.cs.man.ac.uk/fmethods/projects/AHV-PROJECT/ahv-project.html
more ideas for projects
CLASSIFICATION: goes here (see below) SH: Y/N - and if Y, the grading (see below) CM: Y/N - and if Y, the grading BM: Y/N - and if Y, the grading
Project: 000 Supervisor: PJJ
Project description goes here. Must be in HTML format. E.g. paragraphs must be separated by
REFERENCES: delete if none.
COURSE PREREQUISITES: delete if none.
EQUIPMENT: delete if none.