T-79.148 Introduction to Theoretical Computer Science (2 cr)

Autumn 2003

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.

[Current] [General] [Lectures] [Tutorials] [Examination] [Material] [Feedback]

Previous years: [Spring 2003] [Autumn 2002] [Spring 2002] [Spring 2001] [Spring 2000] [Spring 1999] [Spring 1998]

Current

• Keräämme palautetta syksyn 2003 kurssista.
• Please give feedback on the fall 2003 course.
• The exam time has been changed. The December 19 exam starts at 10 o'clock. There was an error in the exam lists. Please register for the exam and do not forget to do the computer exercises BEFORE the exam.
• Registration is over.
• All three rounds of computer assignments have been generated to those who have registered. To do the exercises you need your ID and password. If you have not received your ID and password, please contact Harri Haanpää. There is also an optional 4th round.

General Information

• The course consists of:
  • lectures (2 h per week, in Finnish)
  • tutorials (1 h per week, one group in English)
  • an examination (Fri 19 Dec, 10-13 o'clock).
  There is also an examination on Saturday 25 Oct 2003, and examinations are also planned for February and May 2004. Registration for the examinations by TOPI.

• Registration for the course by TOPI. One of the tutorial groups (indicated below) will be given in English and the rest in Finnish. Registration for the tutorials opens Monday 8 September at noon and closes Friday 26 September at noon.

• In order to pass the course you have to:
  1. complete three compulsory sets of home assignments, and
  2. get a passing grade on the exam, as augmented by credit earned from the tutorials.
  The compulsory assignments are individually computer-generated for each student, and are submitted over the network. Completing these assignments is a mandatory prerequisite for participating in the exam. For more details, see the computerised assignments info page.

• Grading: Exam max 60 points, tutorials max 6 points. Min passing grade approx. 30 points (tolerance 4 p), highest grade (5) approx. 54 points. In the case of "close call" failures (at most 2 points below passing) despite serious study effort (at least 4 tutorial bonus points), there is a possibility of getting a passing grade by solving additional tutorial problems. To discuss this option, please contact the lecturer after the exam has been graded.

• Newsgroup: opinnot.tik.tkt

Lectures

Lecture schedule (tentative):

Lecture	Date	Topic	Sipser	Lewis-Papadimitriou	Lecture slides (in Finnish)
1.	11 Sep	Administration. Review of basic math (functions, relations, induction).	Pp. 1-13, 23-25	1.1-1.3, 1.5	Kalvot (pdf)
2.	18 Sep	Alphabets, strings and languages. Countable and uncountable sets.	Pp. 13-14, 16, 161-164	1.4, 1.7	Kalvot (pdf)
3.	25 Sep	Finite automata.	Pp. 31-43	2.1	Kalvot (pdf)
4.	2 Oct	Automata minimisation. Nondetermistic finite automata.	Pp. 47-58, 275	2.2, 2.5	Kalvot (pdf)
5.	9 Oct	Regular expressions and finite automata.	Pp. 58-76	1.8, 2.3	Kalvot (pdf)
6.	16 Oct	Nonregular languages and the "pumping lemma". Context-free grammars and languages. Regular grammars.	Pp. 77-97	2.4, 3.1	Kalvot (pdf)
7.	23 Oct	Parse trees and derivations. Recursive-descent parsing of LL(1) grammars.	Pp. 97-98	3.2, 3.7 (partly)	Kalvot (pdf)
8.	30 Oct	Chomsky normal form and the CYK parsing algorithm. Pushdown automata.	Pp. 98-114, 240-241	3.3, 3.4, 3.6	Kalvot (pdf)
9.	6 Nov	The context-free pumping ("uvwxy") lemma. Turing machines.	Pp. 115-135	3.5, 4.1	Kalvot (pdf)
10.	11 Nov	Multitrack and multitape Turing machines. Nondeterministic Turing machines. This lecture takes place on 11 Nov at 2 p.m. in lecture hall AS2 in the new Tu/AS building.	Pp. 136-140	4.3, 4.5	Kalvot (pdf)
11.	20 Nov	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	Kalvot (pdf)
12.	27 Nov	The halting problem. Undecidability. Rice's theorem. General and context-sensitive grammars. Linear bounded automata. The Chomsky hierarchy.	Pp. 171-174, 196	5.3, 5.4, 4.6 p. 271	Kalvot (pdf)
13.	4 Dec	Review and discussion of the course material. Exam requirements.

Tutorials

The tutorials start after the first lecture. The last tutorials are on 2-3 Dec.

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

In addition to the voluntary tutorials there are three compulsory computer-generated problem sets. (See the info page.)

The tutorial bonus points and the computer-generated problems expire in one year, i.e., the first exam when they are no longer valid is the corresponding course exam in the following year (approx. Dec 2004). The tutorial bonus points and computer-generated problems must be from the same course installation, e.g., Autumn 2003.

The tutorial bonus points, the Regis bonus points, and the Regis exercises from

• autumn 2002 are valid in all exams up to but not including the December 2003 exam,
  • Exception: The Regis exercises (but not the bonus points) from autumn 2002 remain valid until the February 2004 exam. Thus a student that has started the Regis exercises in autumn 2002 and completed them may take part in all exams up to and including the February 2004 exam.
• spring 2003 are valid in all exams up to but not including the May 2004 exam,
• autumn 2003 are valid in all exams up to but not including the December 2004 exam,
  • This may change if the lecturer changes.
• spring 2004 are valid in all exams up to but not including the May 2005 exam.
  • This may change if the lecturer changes.

The demonstration problems are likely to be at least 90% the same as in the Spring 2003 installation of the course. The demonstration problems are discussed at the tutorials to the extent that time permits.

Updates to the demonstration problems and their solutions are distributed via this site.

Tutorial problems: Electronic copies downloadable here each week. Paper copies available at the lectures, and from the rack outside the theory lab office (TB336).

1. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
2. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
3. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
4. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
5. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
6. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
7. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
8. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
9. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
10. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
11. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)
12. tehtävät (pdf) ratkaisut (pdf) problems (pdf) solutions (pdf)

Tutorial scores.

Note: The demonstration problems and their solutions are for the most part the same as last Spring.

Material

• Lecture Notes: Typeset lecture notes (in Finnish) distributed by Edita.
• Textbook(s): The recommended English textbook for the course is M. Sipser, Introduction to the Theory of Computation (PWS Publishing 1997). The former recommended text, H. Lewis and C. Papadimitriou, Elements of the Theory of Computation (Prentice Hall 1998) is being phased out. Finnish students do not need to purchase the textbook, since the course follows closely the lecture notes. However the Sipser book is very reader-friendly yet insightful, so reading it on the side will help in following the course.
• Supporting material:
  • Demonstration problems and their solutions from the tutorials. Material from Spring 2003 is bundled together with the lecture notes; updates available as the course progresses.
  • Some of the material will be available also via this web page. Please avoid unnecessary printing of this material to save printers, paper and thus nature !!!
  • A short introduction to set theory and relations (by Tommi Syrjänen, in Finnish, ps/ pdf).
  • An example on determinising a finite-state automaton (by Heikki Tauriainen, in Finnish, ps/ pdf).
• Examination requirements will be announced later.
• Mallitentti vm 2001 (ps/ pdf), vastaukset (ps/ pdf). A sample examination from 2001 (ps/ pdf).
• Tentti/exam 11.2.2002: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 8.5.2002: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 12.8.2002: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 28.10.2002: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 17.12.2002: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 3.2.2003: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 7.5.2003: tehtävät (pdf), problems (pdf), tulokset/results.
• Tentti/exam 18.8.2003: tehtävät (pdf), problems (pdf).
• Tentti/exam 25.10.2003: tehtävät (pdf), problems (pdf).

Feedback

Summaries of feedback from previous courses: Spring 2003 Autumn 2002, Spring 2002.

Some fun and possibly relevant links that are not part of the course.

• Clay Mathematics Institute Millennium Prize Problems; note specifically the P vs. NP problem.
• Links to cellular automata applets: 1D cellular automata, Conway's Game of Life, self-replicating CA.