Projects for CS605 practical work
The practical work for CS605 will comprise a significant amount of computer programming and/or theorem proving, with an explanatory report. From the following options each student should pick one:
- Option 1. Analysis of the computational power and/or analysis of the computational complexity of a computer game. This project option is the default option; it is expected the majority of students will pick this option. Each student picks their game(s) to analyse. The game can be one of the list of suitable computer games circulated during lectures, a modification of one of those games, any other suitable existing computer game, a suitable modification of any other existing computer game, an suitable original computer game that you design, or a combination of several suitable games. "Suitable" in the aformentioned sentence means "capable of being analysed for their computational power." An example of an original game was the "swapping the liquid in two vessels" game discussed in detail during lectures. Two examples of modifying existing games were modifications of Tetris and Pong also discussed in detail during lectures. Each of these three games were analysed for their computational power. I also gave an example of a well-known game (Minesweeper) analysed for both its computational power (a variant was shown to be Turing-complete) and its computational complexity (it was shown to be NP-complete). To undertake this project, there is no need to purchase the computer game, or play the computer game, or even have any interest in computer games. Watching a video of the game being played on YouTube and/or reading the rules of the game would be sufficient. Each of the games on the list circulated during lectures has some information on it publicly available on the web. If you choose to analyse an original game, or choose a game not on the list circulated during lectures, then please inform me of the rules of the game in advance (e.g. a link to an appropriate webpage).
- Option 2. The same as above (in particular one is expected to prove theorems about the game and/or variants of the game) except (a) two or more students work together, and (b) the team must implement the game and/or a variant of the game using JavaScript or Python. The source code must be released into the public domain under CC0 or something equivalent. The target audience is schoolchildren (only a very simple game is expected).
Students must submit a report appropriately through Moodle (use appropriate link on CS605 Moodle page, not a Moodle forum message) that includes all proofs completed as part of the project as a single PDF file. In the case of a programming project, the report will contain all user manual(s), for example, combined into a single PDF file. (Extra material (such a software, if part of a programming project) can be submitted separately to email address 
.)
No two students will be allowed to choose the same topic (unless they are part of the same team). Topics will be allocated on a first-come-first-served basis. The chosen topics to date are:
| | | | "Computational analysis of the computer game 'Defender'" |
| | | | "Computational analysis of the computer game 'Tower of Hanoi'" |
| | | | "Computational analysis of the computer game 'Numba'" |
| | | | "Computational analysis of the computer game 'Galaga'" |
How do I choose a topic?
Send an email to my regular email address with your topic choice. When I confirm your choice, you have chosen your topic.
It may be possible to exchange one's topic for another topic, depending on whether the latter is unallocated to another student, and depending on how soon the request is made.
How will the report be marked?
Only reports uploaded appropriately through Moodle (use appropriate link on CS605 Moodle page, not a Moodle forum message) on or before the date and time specified on the CS605 homepage will be marked, unless alternative arrangements have been agreed with me in advance. The report should be in the form of a single PDF document. Students undertaking a programming project should upload the report associated with the project (description of project, user manuals, etc.) through Moodle by this deadline also, and on the same day send any software source code to my regular email address . Emails with source code should include "CS605" in the subject line, and include your full name and student number in the body of the email.
Regarding the expected length of the report, there is no expected length as some complicated proofs can be short. The effort put into the project will be expected to be equivalent to five full days of work, and the projects will be marked assuming each student did invest that amount of effort.
The projects will be marked by giving equal weighting to each of the following four criteria:
- Structure and explanation (e.g. does your report have a beginning middle and end, do you explain the background or context of the work, do you have a conclusion, does each part of the report follow logically from what came before),
- Technical accuracy (e.g. are there flaws, contradictions, or omissions causing ambiguity in the proofs or explanations),
- Demonstration of understanding by incorporating novel information (e.g. your own unique examples, or unique explanations of concepts in your own words), and
- Difficulty of the topic (e.g. did you tackle a problem that would be regarded as challenging at taught masters level).
You must include a list of references, and indicate in your report where everything as part of your submitted project (facts, code, proofs and proof ideas, examples you include to illustrate points, etc.) has come from if it is not your own invention. Marks will be deducted for failures to properly reference such material in your report. This way I can clearly identify what code, examples, proofs, and proof ideas are the novel information that you are offering as your project.
Your report should contain a title, your student number (but not your name), the date you finished writing the report, the module name "CS605", an introduction section that briefly explains what your report is about and stating your assumptions about what the reader knows before reading your report, the body of your report divided into sections where any and all material taken from other sources (e.g. books, websites, lecture notes) is clearly identified with a reference number, a conclusion briefly summarising what was in your report, and a list of references corresponding to the reference numbers used in the body of your report. The particular section names in the body of one's report will vary from project to project, in particular depending on whether one or several games are analysed, whether programming was part of the project, whether the multiple proofs are related or independent, and so on. All of the parts listed in this paragraph should be in a single PDF file.
Good luck!
Last updated 12 Feb 2017, 21:14.