TÖL203F Algorithms, Logic and Complexity
The project involves students picking one subject related to the course material and giving a 20 min. talk.
The talks should be in Powerpoint (or similar) form and they will be placed on the course website afterwards.
The talks will be graded based on four elements: contents, organization, quality of slides, and presentation.
Below is a list of available topics. You can also suggest other topics, but they have to be related to the
course material. Only one student can pick each subject - first come, first gets! You should have picked a
topics before March 3rd.
Some of the topics have a reference linked to it, but if a link is missing then you should be able to get
more information using Google. Also don't hesitate to seek out other references than then one provided.
- Quantum computation - survey of progress [Thomas Bressac]
- Turing completeness - explain it and its significance [Björn]
- How to build a Turing machine in SQL [Ingvi]
- Languages that are designed to be primitive recursive, like LOOP [Arinbjörn]
- Kolmogorov complexity - explain the concept and its usage
- The Ackermann function - describe the function and its computational properties [Jónas]
- Other models of computation, equivalent to the Turing machine, such as
- An Oracle machine is a Turing machine with an oracle - explain and explore its possibilites [Magnus]
- You can also look for recent papers from theoretical computer science conferences:
The presentations will start on monday March 17th.
hh (hja) hi.is, February 24th, 2014.