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 2005

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] [Exams] [Material] [Feedback] [Links]

Previous years: [Autumn 2004] [Spring 2004] [Autumn 2003] [Spring 2003] [Autumn 2002] [Spring 2002] [Spring 2001] [Spring 2000] [Spring 1999] [Spring 1998]

Current

  • A summer exam is arranged on Aug 22. The deadline for registering is Aug 17, 12.00h. Remember that you must complete the Regis assignments before taking the exam.
  • The main exam Spring 2005 is on Tuesday 17th of May (see the exam schedule). The deadline for registering is May 13. Remember that you must complete the Regis assignments before taking the exam.
  • There will be 13 rounds of tutorials this spring. The last round of tutorials is on week 17. Only the groups on Tuesday 26th and Wednesday the 27th will be arranged. Students normaly attending groups on Thursday and Friday should choose one to attend.
  • Week 15, tutorial sessions on Wednesday the 13th of April from 12-14 in Y228 will exceptionally be arranged in room U262.
  • The bonuspoints deadline for the Regis assignments has been postponed by two weeks. The new deadline is the 1st of April at 23.59.
  • The second round of assignments have been generated 14.2.2005. Additionally, assignments for students who attended the Autumn 2004 course have been generated.
  • The first round of computer assignments have been generated 7.2.2005. If you have not received your id and password to the assignments server by email, please contact the course personnel. Students who also attended the Autumn 2004 course will get their assignments on Monday 14.2., when their old assignments expire.
  • The last day to register for the course is on Friday the 4th of February. The registration is needed for the computer assignments. The first batch of assignments will be generated on Monday the 7th of February.
  • Due a technical problem in webtopi, all registrations to the exam 14th of February made before the 27th of January were lost. Please reregister if you intend to take the exam then.
  • The Topi registration is open between 17.1 and 4.2. Please register now.
  • The results for the exam 20.12.2004 are available.
  • 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).

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 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 17 Jan at 9:00 and closes Fri 4 Feb at 16:00.

  • In order to pass the course you have to:
    1. complete four 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 Timo Latvala on Thursdays 2 p.m. - 4 p.m. in Lecture Hall T1 of the Computer Science building. The first lecture is on Thu 20 Jan. 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 2004.

English translations of the lecture slides from Spring 2004 are available here.

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

Tutorials

The tutorials start the week after the first lecture. The last tutorials are on week 17 (26-27.4) (updated, see Current). The Friday 15-16 tutorial is in English, the others are in Finnish. The head assistant of the course is Tommi Syrjänen.

Day Time Location Assistant
Tue 14-15 Y228 Matti Järvisalo
15-16 Y228 Matti Järvisalo
Wed 12-13 Y228 Tommi Syrjänen
13-14 Y228 Tommi Syrjänen
Thu 16-17 Y307 Emilia Oikarinen
17-18 Y307 Emilia Oikarinen
Fri 14-15 F Antti Hyvärinen
15-16 F Antti Hyvärinen In English

TOPI registration for the tutorials opens Mon 17 Jan at 9:00 and closes Fri 4 Feb at 16: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 four compulsory computer-generated "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.

  1. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  2. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  3. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  4. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  5. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  6. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  7. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  8. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  9. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  10. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  11. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  12. tehtävät (pdf) ratkaisut (pdf) problems (pdf)
  13. tehtävät (pdf) problems (pdf)

Tutorial scores.

Validity of tutorial and Regis problems and their bonus points. In general, exams for the course are scheduled for February, May, August, October, and December of each year. As long as that schedule holds:

  • The Regis problems generated in a given autumn / spring semester will be valid until the Feb / 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 / Feb exam in the following year.

Examinations and Grading

In general, exams for the course are scheduled for February, May, August, October, and December of each year. The main course exam in Spring 2005 is scheduled for Tuesday 17th May. There is also an exam scheduled for Monday 14th February, intended mainly for students from previous instantiations of the course.

To participate in an exam, you must first complete your personal computer-aided Regis exercises. See the exam requirements. Remember also to register for the exam. The deadline for registering for the May exam is May 13.

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 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 April 1.

Material

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 will open 2nd of May. The questionare will close on May 20.

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: 15 November 2005. Timo Latvala