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. There are four options from which 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 fifty suitable computer games circulated during lectures, a modification of one of those fifty games, any other existing computer game, a modification of any other existing computer game, an original computer game that you design, or a combination of several games. 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 fifty games on the list circulated during lectures has some information on it publicly available on the WWW. If you choose to analyse an original game, or choose a game not on the list of fifty 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 the Kivy framework for the Python programming language. The Python source code must be submitted.

• Option 3. A programming project, such as one of the examples outlined in lectures. For example, "Define a framework to embed a PDA in the Virtual Turing Machine", "A Python script to preprocess nondeterministic finite automata to run on the Virtual Turing Machine", and "Enumerating the set of syntactically correct X programs + user manual" (where X might be Python or Java or C). The source code must be submitted.

• Option 4. An extension to material covered in lectures, comprising significant original material and original proofs from the author.

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:

			"Enumerating the set of syntactically correct Python programs + user manual"
			"The halting problem in a game, and other proofs"
			"Computational analysis of the computer game 'Kingdom Rush'"
			"Computational analysis of the computer game 'Cogs'"
			"Computational analysis of the computer game 'Plants vs. Zombies'"
			"Computational analysis of the computer game 'Micron'"
			"Proofs that various languages are not context free"
			"Computational analysis of the computer game 'Navigate Robots'"
			"Computational analysis of the computer game 'Block Dude'"
			"Define a framework to embed a PDA in the Virtual Turing Machine"
			"Computational analysis of the computer game 'Kami'"
			"Computational analysis of the computer game 'Bad Piggies'"
			"Computational analysis of the computer game 'Octopus'"
			"Computational analysis of the computer game 'Snake'"
			"Computational analysis of the computer game 'Doodle Jump'"
			"Computational analysis of the computer game 'Feed Me Munchy'"
			"Computational analysis of the computer game 'Chip's Challenge'"
			"Computational analysis of the computer game 'Puzzle Bobble'"
			"Computational analysis of the computer game 'Pipe Mania'"

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.

Only reports uploaded appropriately through Moodle (use appropriate link on CS605 Moodle page, not a Moodle forum message) on or before 23:59h on Sunday 22nd March 2015 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.