TCS / Studies / T-79.148 Introduction to Theoretical Computer Science
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

T-79.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, context-free 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]


Current

  • The course exam is on Tuesday 17 December, 9--12 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, self-replicating CA's. (These are just for fun & interest, not formally part of the course.)

General Information

  • 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, 9-12 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:
    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

Lectures by Prof. Pekka Orponen Thursdays 12-2 p.m. in the Mellin Hall (main building). First lecture on 12 September.

Lecture schedule:
Week Date Topic Sipser Lewis-Papadimitriou Lecture slides (in Finnish)
37.12 Sep Administration. Review of basic math (functions, relations, induction). Pp. 1-13, 23-25 1.1-1.3, 1.5 Kalvot (pdf)
38.19 Sep Alphabets, strings and languages. Countable and uncountable sets. Pp. 13-14, 16, 161-164 1.4, 1.7 Kalvot (pdf)
39.26 Sep Finite automata. Pp. 31-43 2.1 Kalvot (pdf)
40.3 Oct Automata minimisation. Nondetermistic finite automata. Pp. 47-58, 275 2.2, 2.5 Kalvot (pdf)
41.10 Oct Regular expressions and finite automata. Pp. 58-76 1.8, 2.3 Kalvot (pdf)
42.17 Oct Nonregular languages and the "pumping lemma". Context-free grammars and languages. Regular grammars. Pp. 77-97 2.4, 3.1 Kalvot (pdf)
43.24 Oct Parse trees and derivations. Recursive-descent parsing of LL(1) grammars. Pp. 97-98 3.2, 3.7 (partly) Kalvot (pdf)
44.31 Oct Chomsky normal form and the CYK parsing algorithm. Pushdown automata. Pp. 98-114, 240-241 3.3, 3.4, 3.6 Kalvot (pdf)
45.7 Nov The context-free pumping ("uvwxy") lemma. Turing machines. Pp. 115-135 3.5, 4.1 Kalvot (pdf)
46.14 Nov Multitrack and multitape Turing machines. Nondeterministic Turing machines. Pp. 136-140 4.3, 4.5 Kalvot (pdf)
47.21 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)
48.28 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)
49.5 Dec Review and discussion of the course material. Exam requirements.


Tutorials

Day Time Location Assistant
Wed 12-13 Y313 Timo Latvala
13-14 Y313 Timo Latvala
14-15 U358 Mikko Särelä
15-16 U358 Mikko Särelä
16-17 U264 (English) Toni Jussila
Thu 14-15 U358 Matti Järvisalo
15-16 U358 Matti Järvisalo
Fri 12-13 U358 Tommi Syrjänen
13-14 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 computer-generated 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 13-14) 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).

  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. 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 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 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 finite-state 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.