
T79.1001 Introduction to Theoretical Computer Science T (4 cr)
Spring 2006
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 course T79.1001 replaces the earlier course
T79.148 Introduction to Theoretical Computer Science
.
[Current]
[General]
[Lectures]
[Tutorials]
[Exams]
[Material]
[Feedback]
[Links]
Previous years:
[Autumn 2005]
[Spring 2005]
[Autumn 2004]
[Spring 2004]
[Autumn 2003]
[Spring 2003]
[Autumn 2002]
[Spring 2002]
[Spring 2001]
[Spring 2000]
[Spring 1999]
[Spring 1998]
 [4 May 2006] Please provide feedback on the course via the
DCSE department's
course feedback system. Filling in the feedback form is
rewarded by one bonus exam point, used to increase any passing
grade earned from the course.
The electronic questionnaires open Fri 5 May and close Mon 22 May.
 [4 May 2006] The course exam is on Friday 19 May, 36 p.m.
Check the time and place still from the departmental
exam schedule,
remember to register for the exam via
TOPI by Sun 14 May, and note that all your
Regis assignments must be completed by the exam date 
otherwise your exam paper will not be graded (really!).
 [6 Apr 2006] Because of the Easter break, there
is no lecture on Thu 13 April, and correspondingly no
tutorial sessions on 1819 April.
 [22 Mar 2006] New sets of Regis assignments have now
been generated for those students who started the
course in Autumn 2005, are continuing in Spring 2006,
and did not complete their old problem sets by the
9 Mar 2006 expiration deadline.
 [17 Mar 2006] Validation of Regis assignments
generated in Autumn 2005 or earlier has now been
suspended. All participants in the Spring 2006
course should by now have new assignments, generated
on or after 3 Feb 2006.
 [4 Mar 2006] The departmental course feedback questionnaires
for courses in period III/2006 are accessible
here from Fri 3 Mar until Fri 17 Mar.
If you are taking the short version of the course (T79.1002),
please reply; you will rewarded by an exam bonus point
(cf. below).
The feedback questionnaires for the long version of the
course (T79.1001) will open in May.
 [26 Feb 2006] After the exam week break, lectures for the
course resume in week 11 (16 Mar), and tutorials correspondingly
in week 12 (2122 Mar).
 [23 Feb 2006] There are no lectures on the course in week 9
(27 Feb  3 Mar), but the tutorial sessions are arranged as usual.
Week 10 (610 Mar) is exam week, and this course has neither
lectures nor tutorials on that week. The final exam for the
short version (T79.1002, 2 cr) of the course takes place on
Thu 9 Mar. You must register for the exam via the
TOPI system by Mon 6 Mar 8 a.m.
All the compulsory Regis
problems must have been solved by the time of the exam.
The exam for the long version of the course (T79.1001, 4 cr
takes place on Fri 19 May. Participants in the long version of the
course should NOT go to the exam on 9 Mar. (Exception: the repeat
exam for the participants of T79.1001 from Autumn 2005 takes
place on that date.)
 [3 Feb 2006] The computerised Regis/Stratum assignments
have now been generated for all new students registered
for the course. For further information,
see the general computerised assignments
info page.
 [3 Jan 2006] First lecture Thu 19 Jan 25 p.m., Lecture Hall T1.
Note that the first lecture is exceptionally 3 hrs long.
 [3 Jan 2006] Registration via TOPI
opens Mon 16 Jan at 9:00 and closes Fri 27 Jan at 18:00.
Registration is compulsory.
 [3 Jan 2006] Recommended reading for Finnish students:
Ajankäyttötutkimuksen satoa eli miten saan ystäviä,
menestystä ja hyvän arvosanan tietojenkäsittelyteorian
perusteista by Harri Haanpää
(a statistical analysis of factors affecting course
performance in Spring 2004, in Finnish).
 [3 Jan 2006] Next exam for the Autumn 2005 and earlier
versions of the course on Thu 9 March. Registration via
TOPI.
All compulsory Regis assignments must have been completed
before participating in the exam.
 The course consists of:
 lectures (2 h per week, in Finnish)
 tutorials (1 h per week, one group in English)
 an examination
 Registration for the course is by
TOPI.
You must register in
order to take the course, even if you were
not intending to attend the lectures or the
tutorials. (Registrations are needed for bookkeeping
purposes, specifically for generating your set of
computerised home assignments; see below.)
One of the tutorial groups (indicated below)
will be given in English and the rest in Finnish.
Registration for the tutorials opens
Mon 16 Jan at 9:00 and closes Fri 27 Jan at 18:00.
 In order to pass the course you have to:
 complete four 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.
 Newsgroup:
opinnot.tik.tkt
Lectures by
Pekka Orponen on
Thursdays 2 p.m.  4 p.m. in Lecture Hall T1 of the Computer Science
building. The first lecture is on Thu 19 Jan, and is exceptionally
three hours long (2  5 p.m.)
The lectures are in Finnish, and the slides will appear here
after each lecture.
The contents will likely be very close to those from previous years,
e.g. Autumn 2005.
English translations of the lecture slides from Spring 2004 are
available here.
Lecture schedule (tentative):
Week  Date  Topic 
Sipser  LewisPapadimitriou 
Lecture slides (in Finnish) 
3.  Jan 19 
Review of basic mathematics (functions, relations, induction).
Alphabets, strings and languages. 
Pp. 116, 2325  1.11.3, 1.5, 1.7 
PostScript PDF 
4.  Jan 26 
Finite automata. 
Pp. 3143  2.1 
PostScript PDF 
5.  Feb 2 
Automata minimisation. Nondeterministic finite automata. 
Pp. 4758, 275  2.2, 2.5 
PostScript PDF 
6.  Feb 9 
Regular expressions and finite automata. 
Pp. 5876  1.8, 2.3 
PostScript PDF 
7.  Feb 16 
Contextfree grammars and languages.
Regular grammars. 
Pp. 9198  3.1 
PostScript PDF 
8.  Feb 23 
Parse trees and derivations.
Recursivedescent parsing of LL(1) grammars. 
  3.2, 3.7 (partly) 
PostScript PDF 
9.  Mar 2 
No lecture. 
10.  Mar 9 
Exam week; no lecture. 
11.  Mar 16 
Chomsky normal form and the
CYK parsing algorithm.
Pushdown automata. 
Pp. 98114, 240241  3.3, 3.4, 3.6 
PostScript PDF 
12.  Mar 23 
Countable and uncountable sets.
The halting problem.
Regular and contextfree pumping lemmata. 
Pp. 7783, 115119, 161164  1.4, 2.4, 3.5 
PostScript PDF 
13.  Mar 30 
Turing machines: standard, multitrack and multitape.
Nondeterministic Turing machines. 
Pp. 125140  4.1, 4.3, 4.5 
PostScript PDF 
14.  Apr 6 
Recursive and recursively enumerable languages.
Turing machine encoding and universal Turing machines. 
142143,  4.2, 5.1, 5.2, 5.7 
PostScript PDF 
15.  Apr 13 
Easter vacation; no lecture. 
16.  Apr 20 
Undecidability. Rice's theorem. 
159168, 171174, 196  5.3, 5.4 
PostScript PDF 
17.  Apr 27 
General and contextsensitive grammars.
Linear bounded automata. The Chomsky hierarchy. 
  4.6 p. 271 
PostScript PDF 
18.  May 4 
Review and discussion of the course material.
Exam requirements.

Tutorials
The tutorials start the week after the first lecture.
The Wednesday 1617 tutorial session is given in English, the others are in Finnish. The head assistant
of the course is
Tommi Syrjänen.
Day  Time 
Location  Assistant 
Tue  1011  F  Matti Järvisalo 
 1112  F  Matti Järvisalo 
 1415  Y228  Vesa Ojala 
 1516  Y228  Vesa Ojala 
Wed  1213  Y228  Antti Hyvärinen 
 1314  Y228  Antti Hyvärinen 
 1617  J  Tommi Syrjänen  (In English) 
 1718  J  Tommi Syrjänen 
TOPI registration
for the tutorials opens
Mon 16 Jan at 9:00 and closes Fri 27 Jan at 18:00.
You must register in order to
take the course, even if you were not intending to
physically attend the tutorials. (Registrations are
needed for bookkeeping purposes, specifically for
generating your set of computerised home assignments;
see below.)
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 home assignments
is as follows:
Problems solved  Bonus points 
5  1 
10  2 
15  3 
20  4 
25  5 
30  6 
The demonstration problems are likely to be 90% the same as
in the previous instalment of the course,
and are discussed at the tutorials to the extent that time permits.
In addition to the voluntary tutorials there are
three compulsory computergenerated "Regis" problem sets.
(See the info page.)
Tutorial problems: Electronic copies downloadable here
each week. Paper copies available at the
lectures, and from the rack outside the theory lab office
(TB336).
Solutions for the demonstration problems are provided here
as the course progresses.
 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.
Validity of tutorial and Regis problems and their bonus points.
Exams for the course are for the time being scheduled for examination
periods 1, 2, 3, 5 and 6 of the academic year (August, October, December,
March, May). As long as that schedule holds:

The Regis problems generated in a given autumn / spring semester
will be valid until the Mar / Oct exam in the following semester.

Fully completed Regis assignments, and any bonus points earned
in a given autumn / spring semester will
be valid until the Oct / Mar exam in the following year.
Examinations and Grading
In general, exams for the course are scheduled for March,
May, August, October, and December of each year.
The main course exam in Spring 2006 is
scheduled for Fri 19 May.
There is also an exam for other instantiations of
the course, scheduled for Thu 9 March.
To participate in an exam, you must first complete your
personal computeraided Regis exercises. See the
exam requirements.
Remember also to register
for the exam.
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.
Bonus points earned from the tutorials are added directly
to the exam points, and may help to change the exam grade
from failing to passing. Bonus points earned from Regis/Stratum
assignments completed on time (see the info page) are only added
afterwards to a passing exam grade, and may thus help to increase
the grade, but not pass the course. Note that the Regis assignments
must in any case be completed before the exam, and extra points
are awarded only for completion by the bonus deadline of
March 9, 4 p.m.
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 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 Autumn 2004 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 finitestate automaton
(by Heikki Tauriainen, in Finnish, ps/
pdf.
 An introduction to pumping lemmata and their uses
(by Tommi Syrjänen, in Finnish, ps/
pdf.
 Solutions for one old examination (25.10.2003), in Finnish,
ps/
pdf.
 Examination requirements are available.
 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),
tulokset/results.
 Tentti/exam 25.10.2003:
tehtävät
(pdf),
problems
(pdf),
tulokset/results
ratkaisut
(pdf).
 Tentti/exam 19.12.2003:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
 Tentti/exam 16.2.2004:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
 Tentti/exam 13.5.2004:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 23.8.2004:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 23.10.2004:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 20.12.2004:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 14.02.2005:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 17.05.2005:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 22.08.2005:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 27.10.2005:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 14.12.2005:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 9.3.2006:
tehtävät (pdf),
problems (pdf),
tulokset/results.
 Tentti/exam 19.5.2006:
tehtävät (pdf),
problems (pdf),
tulokset/results.
Feedback
Please provide feedback on the course via the DCSE department's
course feedback system. Filling in the feedback form is
rewarded by one bonus exam point, used to increase any passing
grade earned from the course.
The feedback system for course T79.1002
opens Fri 3 March and closes Fri 17 Mar.
The feedback system for course T79.1001
opens Fri 5 May and closes Mon 22 May.
Summaries of feedback from previous courses:
Autumn 2003
Spring 2003
Autumn 2002,
Spring 2002.
Links
Some fun links that are related to the course contents, but
not part of the official course material.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 31 July 2006.
Pekka Orponen
