
T79.1001 Introduction to Theoretical Computer Science T (4
cr)
Autumn 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 .
Starting in 2006/07, the course is lectured in the autumn semester only.
[Current]
[General]
[Lectures]
[Tutorials]
[Exams]
[Material]
[Feedback]
[Links]
Previous years:
[Spring 2006]
[Autumn 2005] [Spring 2005] [Autumn 2004] [Spring 2004]
[Autumn 2003]
[Spring 2003]
[Autumn 2002]
[Spring 2002]
[Spring 2001]
[Spring 2000]
[Spring 1999]
[Spring 1998]
 The course consists of:
 lectures (2 h per week, in Finnish)
 tutorials (2 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 Sep 1 at 9:00 and closes
28 Sep 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 Harri
Haanpää on
Thursdays 2 p.m.  4 p.m. in Lecture Hall T1 of the Computer Science
building. The first lecture is on Thu 14 Sep.
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. Spring
2006.
Lecture schedule (tentative):
Lecture

Date 
Topic 
Sipser 
LewisPapadimitriou 
1

Sep 14

Review of basic mathematics (functions, relations,
induction). Alphabets, strings and languages. 
Pp. 116, 2325 
1.11.3, 1.5, 1.7 
2

Sep 21

Finite automata. 
Pp. 3143 
2.1 
3

Sep 28

Automata minimisation. Nondeterministic finite automata. 
Pp. 4758, 275 
2.2, 2.5 
4

Oct 5

Regular expressions and finite automata. 
Pp. 5876 
1.8, 2.3 
5

Oct 12

Contextfree grammars and languages. Regular grammars. 
Pp. 9198 
3.1 
6

Oct 19

Parse trees and derivations. Recursivedescent parsing
of LL(1) grammars. 
 
3.2, 3.7 (partly) 

Oct 26

Exam week; no lecture. 
7

Nov 2

Chomsky normal form and the CYK parsing algorithm.
Pushdown automata. 
Pp. 98114, 240241 
3.3, 3.4, 3.6 
8

Nov 9

Countable and uncountable sets. The halting problem.
Regular and contextfree pumping lemmata. 
Pp. 7783, 115119, 161164 
1.4, 2.4, 3.5 
9

Nov 16

Turing machines: standard, multitrack and multitape.
Nondeterministic Turing machines. 
Pp. 125140 
4.1, 4.3, 4.5 
10 
Nov 23

Recursive and recursively enumerable languages. Turing
machine encoding and universal Turing machines. 
142143, 
4.2, 5.1, 5.2, 5.7 
11 
Nov 30

Undecidability. Rice's theorem. 
159168, 171174, 196 
5.3, 5.4 
12 
Dec 7

General and contextsensitive grammars. Linear bounded
automata. The Chomsky hierarchy. 
 
4.6 p. 271 
13 
N/A

Review and discussion of the course material. Exam
requirements. 
Tutorials
The tutorials start the week after the first lecture.
The Tuesday 1618 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 
Mon

1214 
U358

Emilia Oikarinen

(In period I only) 

1416 
U358

Tommi Syrjänen

(In period I only) 
Tue

1214 
Y228 
Tuomas Launiainen


1618 
Y405 
Tommi Syrjänen 
(In English) 
Wed 
1214 
Y313 
Petri Savola 

1416 
U264 
Emilia Oikarinen 
TOPI registration
for the tutorials opens Friday 1 September at 9:00 and closes Thursday 28 September 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 (2 to 4) 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 on T course 
Bonus points on Y course 
04

2

1

59 
1

0

1014 
0

1

1519 
1

2

2024 
2

N/A

2529 
3

30 
4

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 (in PDF) 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
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions

tehtävät
ratkaisut
problems
solutions
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).
 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.
In 2006/07 exams are scheduled
for 30 Aug, 26 Oct, 21 Dec, 6 Mar and 10 May.
The December exam is the main exam for T79.1001 and the October exam
is the main exam for T79.1002.
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 2...4 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 half of
the tutorial exercises done), 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 change the exam grade
from failing to passing or vice versa. 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 Oct 26 1 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). 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. The former
recommended text, H. Lewis and C.
Papadimitriou, Elements of the Theory of Computation (Prentice
Hall 1998) is being phased out.
 Supporting material:
 Demonstration problems and their solutions from the
tutorials will be provided 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.
 Previous exams of
the T79.1001 course
 Previous exams of
the old T79.148 course
Feedback
Please provide feedback on the course via the DCSE department's course
feedback system. at the end of the course.
Links
Some useful and 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: 09 February 2007.
Harri Haanpää
