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)

Spring 2004

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: [Autumn 2003] [Spring 2003] [Autumn 2002] [Spring 2002] [Spring 2001] [Spring 2000] [Spring 1999] [Spring 1998]


Current

  • A quick and dirty translation of lecture slides now also available in English (22 Mar).
  • Exercise groups H8 (Wed 15-16) and H10 (Wed 17-18) cancelled after January. There will still be tutorials in groups H8 and H10 on January 28th. Please unregister from these groups and register for an alternative tutorial group.
  • Registration for the course (by TOPI) has been opened.

General Information

  • 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 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 12 January and closes Friday 30 January.

  • 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.

  • Newsgroup: opinnot.tik.tkt


Lectures

Lectures by Harri Haanpää Thursdays 2 p.m.-4 p.m. in Lecture Hall T1 (Computer Science building). First lecture on January 15. The slides will appear here after each lecture.

A quick and dirty translation of lecture slides now also available in English.

Lecture schedule (tentative):
Lecture Date Topic Sipser Lewis-Papadimitriou Lecture slides (in Finnish)
1.Jan 15 Administration. Review of basic math (functions, relations, induction). Pp. 1-13, 23-25 1.1-1.3, 1.5 PostScript PDF
2.Jan 22 Alphabets, strings and languages. Countable and uncountable sets. Pp. 13-14, 16, 161-164 1.4, 1.7 PostScript PDF
3.Jan 29 Finite automata. Pp. 31-43 2.1 PostScript PDF
4.Feb 5 Automata minimisation. Nondetermistic finite automata. Pp. 47-58, 275 2.2, 2.5 PostScript PDF
5.Feb 12 Regular expressions and finite automata. Pp. 58-76 1.8, 2.3 PostScript PDF
6.Feb 19 Nonregular languages and the "pumping lemma". Context-free grammars and languages. Regular grammars. Pp. 77-97 2.4, 3.1 PostScript PDF
7.Feb 26 Parse trees and derivations. Recursive-descent parsing of LL(1) grammars. Pp. 97-98 3.2, 3.7 (partly) PostScript PDF
8.Mar 4 Chomsky normal form and the CYK parsing algorithm. Pushdown automata. Pp. 98-114, 240-241 3.3, 3.4, 3.6 PostScript PDF
9.Mar 11 The context-free pumping ("uvwxy") lemma. Turing machines. Pp. 115-135 3.5, 4.1 PostScript PDF
10.Mar 18 Multitrack and multitape Turing machines. Nondeterministic Turing machines. Pp. 136-140 4.3, 4.5 PostScript PDF
11.Mar 25 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 PostScript PDF
12.Apr 1 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 PostScript PDF
Apr 8 Easter break
13.Apr 15 Review and discussion of the course material. Exam requirements. Last lecture.


Tutorials

The tutorials start after the first lecture. The last tutorials are on 20-21 Apr. The Tuesday 16-17 tutorial session is in English, the others are in Finnish.

Day Time Location Assistant
Tue 12-13 Y228 Tommi Syrjänen
13-14 Y228 Tommi Syrjänen
16-17 Y405 Matti Järvisalo in English
17-18 Y405 Matti Järvisalo
Wed 12-13 Y313 Pauli Aho
13-14 Y313 Mikko Särelä
14-15 U358 Mikko Särelä
15-16 U358 Cancelled
16-17 K Pauli Aho
17-18 K Cancelled

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.


Examinations

The main course exam is scheduled for May 13, 2004. There is also an exam scheduled for Feb 16, 2004.

To participate in an exam, you must first complete your personal computer-aided Regis exercises. See the exam requirements.

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.

In general, exams are scheduled for February, May, August, October, and December of each year. As long as that schedule holds,

  • Regis exercises started in spring 2003 or earlier / autumn 2003 / spring 2004, and possible bonus points from Regis exercises, will be valid until the Feb 2004 / Oct 2005 / Feb 2005 exam.
  • Tutorial bonus points from spring 2003 / autumn 2003 / spring 2004 will be valid until the Feb 2004 / Oct 2005 / Feb 2005 exam.

The demonstration problems are likely to be at least 90% the same as in the previous 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)
  13. 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 Autumn.


Material


Feedback

Feedback is collected at the end of the course using an electronic questionnaire.

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


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


[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 30 August 2004. Harri Haanpää.