This introductory course on the theory of computation covers the basic aspects of finite automata and regular languages, context-free grammars and pushdown automata, Turing machines and computability theory.
Week | Date | Topic | Sipser | Lewis-Papadimitriou | Other |
1. | 25 Jan | Administration. Review of basic math (functions, relations, induction). | Pp. 1-13, 23-25 | 1.1-1.3, 1.5 | Kalvot (pdf), Syrjänen (pdf) |
2. | 1 Feb | Alphabets, strings and languages. Countable and uncountable sets. | Pp. 13-14, 16, 161-164 | 1.4, 1.7 | Kalvot (pdf) |
3. | 8 Feb | Finite automata. | Pp. 31-43 | 2.1 | Kalvot (pdf) |
4. | 15 Feb | Automata minimisation. Nondetermistic finite automata. | Pp. 47-58, 275 | 2.2, 2.5 | Kalvot (pdf) |
5. | 22 Feb | Regular expressions and finite automata. | Pp. 58-76 | 1.8, 2.3 | Kalvot (pdf) |
6. | 1 Mar | Nonregular languages and the "pumping lemma". Context-free grammars and languages. Regular grammars. | Pp. 77-97 | 2.4, 3.1 | Kalvot (pdf) |
7. | 8 Mar | Parse trees and derivations. Recursive-descent parsing of LL(1) grammars. | Pp. 97-98 | 3.2, 3.7 (partly) | Kalvot (pdf) |
8. | 15 Mar | Chomsky normal form and the CYK parsing algorithm. Pushdown automata. | Pp. 98-114 | 3.3, 3.4, 3.6 | Kalvot (pdf) |
9. | 22 Mar | The context-free pumping ("uvwxy") lemma. Turing machines. | Pp. 115-135 | 3.5, 4.1 | Kalvot (pdf) |
- | 29 Mar | Easter vacation. No lecture. | - | - | - |
10. | 5 Apr | Multitrack and multitape Turing machines. Nondeterministic Turing machines. | Pp. 136-140 | 4.3, 4.5 | Kalvot (pdf) |
11. | 12 Apr | Recursive and recursively enumerable languages. Turing machine encoding and universal Turing machines. | Pp. 142-145, 159-168 | 4.2, 5.1, 5.2, 5.7 (partly) | Kalvot (pdf) |
12. | 19 Apr | The halting problem. Undecidability. Rice's theorem. Recursive functions. Recursive reductions and RE-completeness. | Pp. 171-174, 190-193, 196 | 5.3, 5.4 | Kalvot (pdf) |
13. | 26 Apr | General and context-sensitive grammars. Linear bounded automata. The Chomsky hierarchy. | - | 4.6, p. 271 | Kalvot (pdf) |
14. | 3 May | Review and discussion of the course material. Exam requirements. | - | - |
Day | Time | Location | Assistant |
Tue | 12-13 | Y228 | Timo Latvala |
13-14 | Y228 (English) | Timo Latvala | |
14-15 | Y228 | Emilia Oikarinen | |
15-16 | Y228 | Emilia Oikarinen | |
16-17 | U358 | Mikko Särelä | |
17-18 | U358 (English) | Mikko Särelä | |
Wed | 12-13 | Y228 | Tommi Syrjänen |
13-14 | Y228 | Tommi Syrjänen | |
14-15 | Y427B | Toni Jussila | |
15-16 | Y427B | Toni Jussila | |
16-17 | Y228 | Matti Järvisalo | |
17-18 | Y228 | Matti Järvisalo | |
Thu | 12-13 | Y427A | Elina Parviainen |
13-14 | Y427A | Elina Parviainen | |
14-15 | Y405 | Tuomo Pyhälä | |
15-16 | Y405 | Tuomo Pyhälä |
In the tutorials, there will be three home assignments and two or three demonstration problems each week. The tutorials are not compulsory, but bonus exam points (max 6) will be awarded for doing the home assignments and marking them as done at the tutorial sessions. The grading scheme for the tutorials is as follows:
Problems solved | Bonus points |
5 | 1 |
10 | 2 |
15 | 3 |
20 | 4 |
25 | 5 |
30 | 6 |
However, it is not possible to change the exam grade from 0 to 1 with bonus points, so you have to get enough normal exam points to pass the course. The tutorial bonus points awarded expire in one year, i.e. they are valid up to but not including the next "prime" course exam (approx. May 2003). Solutions to the demonstration exercises will be provided at the tutorial sessions, and afterwards also on this site.
Tutorial problems: Electronic copies downloadable here on the Wednesday of each week. Paper copies available at the lectures, and from the rack outside the theory lab office (TB336).
Tutorial results.