
T79.148 Introduction to Theoretical Computer Science (2 cr)
Autumn 2002
This introductory course on the theory of computation covers
the basic aspects of finite automata and regular languages,
contextfree grammars and pushdown automata, Turing machines
and computability theory.
The autumn installation of the course is primarily oriented
towards other than T students  especially S students
are welcome. However also T students may participate, if the
course fits into their schedule.
[Current]
[General]
[Lectures]
[Tutorials]
[Material]
[Feedback]
Previous years:
[Spring 2002]
[Spring 2001]
[Spring 2000]
[Spring 1999]
[Spring 1998]
 The course exam is on Tuesday 17 December, 912 a.m.
Remember to register for the exam via
TOPI,
and note that all your
Regis assignments
must be completed by the exam date  otherwise your exam paper
will not be graded (really!). Please fill in and return also the
computerised course
feedback form.
(English form here.)
If you submit the form by 22 December, you earn
an extra exam point that counts towards increasing your grade
in case you pass the course. The feedback is processed
anonymously, i.e. the computerised feedback system removes
the student id's from the forms and provides them as a separate
list only for credit assignment purposes.
 A link to the
Clay
Mathematics Institute Millennium Prize Problems
discussed at the lecture on 14 Nov.
(Note specifically the
P vs. NP problem.)
 Links to the cellular automata applets
presented at the end of the lecture on
Thu 3 Oct:
general CA's,
selfreplicating CA's.
(These are just for fun & interest,
not formally part of the course.)
 The course consists of:
 lectures (2 h per week, in Finnish)
 tutorials (1 h per week, one group in English)
 an examination (Tue 17 Dec, 912 KL+T1)
 Registration by
TOPI.
You should register both for the lectures and for a tutorial group.
One of the tutorial groups (indicated below)
will be given in English and the rest in Finnish.
Registration for the tutorials opens
Thursday 5 September at 9:00 and closes
Friday 13 September at 18:00.
 In order to pass the course you have to:
 complete three compulsory sets of home assignments, and
 get a passing grade on the exam, as augmented by
credit earned from the tutorials.
The compulsory assignments are individually computergenerated
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 by Prof.
Pekka Orponen
Thursdays 122 p.m. in the Mellin Hall (main building).
First lecture on 12 September.
Lecture schedule:
Week  Date  Topic 
Sipser  LewisPapadimitriou 
Lecture slides (in Finnish) 
37.  12 Sep 
Administration. Review of basic math (functions, relations, induction). 
Pp. 113, 2325  1.11.3, 1.5 
Kalvot (pdf)

38.  19 Sep 
Alphabets, strings and languages. Countable and uncountable sets. 
Pp. 1314, 16, 161164  1.4, 1.7 
Kalvot (pdf)

39.  26 Sep 
Finite automata. 
Pp. 3143  2.1 
Kalvot (pdf)

40.  3 Oct 
Automata minimisation. Nondetermistic finite automata. 
Pp. 4758, 275  2.2, 2.5 
Kalvot (pdf)

41.  10 Oct 
Regular expressions and finite automata. 
Pp. 5876  1.8, 2.3 
Kalvot (pdf)

42.  17 Oct 
Nonregular languages and the "pumping lemma".
Contextfree grammars and languages. Regular grammars. 
Pp. 7797  2.4, 3.1 
Kalvot (pdf)

43.  24 Oct 
Parse trees and derivations.
Recursivedescent parsing of LL(1) grammars. 
Pp. 9798  3.2, 3.7 (partly) 
Kalvot (pdf)

44.  31 Oct 
Chomsky normal form and the
CYK parsing algorithm.
Pushdown automata. 
Pp. 98114, 240241  3.3, 3.4, 3.6 
Kalvot (pdf)

45.  7 Nov 
The contextfree pumping ("uvwxy") lemma.
Turing machines. 
Pp. 115135  3.5, 4.1 
Kalvot (pdf)

46.  14 Nov 
Multitrack and multitape Turing machines.
Nondeterministic Turing machines. 
Pp. 136140  4.3, 4.5 
Kalvot (pdf)

47.  21 Nov 
Recursive and recursively enumerable languages.
Turing machine encoding and universal Turing machines. 
Pp. 142145, 159168  4.2, 5.1, 5.2, 5.7 
Kalvot (pdf)

48.  28 Nov 
The halting problem. Undecidability. Rice's theorem.
General and contextsensitive grammars.
Linear bounded automata. The Chomsky hierarchy. 
Pp. 171174, 196  5.3, 5.4, 4.6 p. 271 
Kalvot (pdf)

49.  5 Dec 
Review and discussion of the course material.
Exam requirements.

Tutorials
Day  Time 
Location  Assistant 
Wed  1213  Y313  Timo Latvala 
 1314  Y313  Timo Latvala 
 1415  U358  Mikko Särelä 
 1516  U358  Mikko Särelä 
 1617  U264 (English)  Toni Jussila 
Thu  1415  U358  Matti Järvisalo 
 1516  U358  Matti Järvisalo 
Fri  1213  U358  Tommi Syrjänen 
 1314  U358 (Demo/Q&A)  Tommi Syrjänen 
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 computergenerated problem sets.
(See the info page.)
The tutorial bonus points awarded expire in
one year, i.e. they are valid
up to but not including the corresponding course exam in
the following year (approx. Dec 2003).
The demonstration problems are likely to be 90% the same
as in the Spring 2002 installation of the course.
The Spring 2002 problem sets and their solutions are
bundled together with the lecture notes, and can be ordered from
Edita. The demonstration problems are discussed at the
tutorials to the extent that time permits. In addition,
each week's last tutorial group (#9, Fri 1314) is dedicated
to a discussion of the demonstration problems and other
questions raised by the preceding week's material.
Updates to the demonstration problems and their solutions
are distributed via this site.
Tutorial problems: Electronic copies downloadable here
on the Thursday of each week. Paper copies available at the
lectures, and from the rack outside the theory lab office
(TB336).
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
 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.
Table of contents for the notes available
here
(pdf).
 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 readerfriendly
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 2002 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 finitestate automaton
(by Heikki Tauriainen, in Finnish, ps/
pdf).
 Examination requirements from Spring 2002.
 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.
Feedback
Feedback is collected at the end of the course using
an electronic
questionnaire.
(English form here).
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 22 September 2004.
Pekka Orponen.
