T-79.1001 Introduction to Theoretical Computer Science T (4 cr)

Autumn 2007

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 course T-79.1001 replaces the earlier course T-79.148 Introduction to Theoretical Computer Science .

Starting in 2006/07, the course is lectured in the autumn semester only.

[Current] [General] [Lectures] [Tutorials] [Computer exercises] [Exams] [Material] [Feedback] [Links]

Previous years: [Autumn 2006] [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]

Current

• Participants of the autumn 2007 course, please give feedback between Dec 10 and Jan 7 (but after taking the exam).
• Statistics and list of students who passed the computer exercises are now updated hourly. The links on those pages are broken, sorry; by inserting T-79.1001 at the right place you can get where you wanted to.
• Remember to follow the course newsgroup opinnot.tik.tkt (WWW interface) for announcements

General Information

• The course consists of:
  • lectures (2 h per week, in Finnish)
  • tutorials (2 h per week, one group in English)
  • compulsory computer exercises
  • 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 Sep 26 at 18:00.

• In order to pass the course you have to:
  1. first complete four compulsory sets of computerized home assignments, and
  2. second get a passing grade on the exam, as augmented by credit earned from the tutorials.
  The compulsory computer exercises are individually computer-generated for each student, and are submitted over the network.
• Newsgroup: opinnot.tik.tkt

Lectures

• Lecture slides from Autumn 2007
• English translations of the lecture slides from Spring 2004

Lecture schedule (tentative):

Lecture	Date	Topic	Sipser	Lewis-Papadimitriou
1	Sep 11	Review of basic mathematics (functions, relations, induction). Alphabets, strings and languages.	Pp. 1-16, 23-25	1.1-1.3, 1.5, 1.7
2	Sep 18	Finite automata.	Pp. 31-43	2.1
3	Sep 25	Automata minimisation. Nondeterministic finite automata.	Pp. 47-58, 275	2.2, 2.5
4	Oct 2	Regular expressions and finite automata.	Pp. 58-76	1.8, 2.3
5	Oct 9	Context-free grammars and languages. Regular grammars.	Pp. 91-98	3.1
6	Oct 16	Parse trees and derivations. Recursive-descent parsing of LL(1) grammars.	-	3.2, 3.7 (partly)
7	Oct 23	Chomsky normal form and the CYK parsing algorithm. Pushdown automata.	Pp. 98-114, 240-241	3.3, 3.4, 3.6
	Oct 30	Exam week; no lecture.
8	Nov 6	Countable and uncountable sets. The halting problem. Regular and context-free pumping lemmata.	Pp. 77-83, 115-119, 161-164	1.4, 2.4, 3.5
9	Nov 13	Turing machines: standard, multitrack and multitape. Nondeterministic Turing machines.	Pp. 125-140	4.1, 4.3, 4.5
10	Nov 20	Recursive and recursively enumerable languages. Turing machine encoding and universal Turing machines.	142-143,	4.2, 5.1, 5.2, 5.7
11	Nov 27	Undecidability. Rice's theorem.	159-168, 171-174, 196	5.3, 5.4
12	Dec 4	General and context-sensitive grammars. Linear bounded automata. The Chomsky hierarchy.	-	4.6 p. 271
13	Dec 11	Review and discussion of the course material. Exam requirements.

Tutorials

The tutorials start after the first lecture. The Thursday 16-18 tutorial session is given in English, the others are in Finnish. The head assistant of the course is Tommi Syrjänen. There are no tutorials during the exam week from Oct 25 to Oct 31.

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

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
0-4	-2
5-9	-1
10-14	+0
15-19	+1
20-24	+2
25-29	+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 compulsory computer-generated "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.

1. tehtävät ratkaisut problems solutions
2. tehtävät ratkaisut problems solutions
3. tehtävät ratkaisut problems solutions
4. tehtävät ratkaisut problems solutions
5. tehtävät ratkaisut problems solutions
6. tehtävät ratkaisut problems solutions
7. tehtävät ratkaisut problems solutions
8. tehtävät ratkaisut problems solutions
9. tehtävät ratkaisut problems solutions
10. tehtävät ratkaisut problems solutions
11. tehtävät ratkaisut problems solutions
12. tehtävät ratkaisut problems solutions

Tutorial scores.

Validity of tutorial 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). Any tutorial points earned in an autumn semester will be valid up to and including the October exam in the next autumn semester.

Computer exercises

To participate in an exam, you must first complete your computer exercises. Exercises are generated at the beginning of the course after registration is closed for those who have registered for the course. If you complete the computer exercises by the early bird deadline announced in the registration email, you can earn 2 bonus points to augment your grade in the exam. See the info page for details.

• The computer assignments generated in a given autumn semester can be completed until August next summer.
• Fully completed computer assignments will be valid until the October exam the following autumn.

Examinations and Grading

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.

Grading: Exam max 60 points, tutorials -2...+4 points. Min passing grade approx. 50% of exam max, highest grade (5) approx 90%. 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 successfully solving additional 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 computerized 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 computerized assignments must in any case be completed before the exam, and extra points are awarded only for completion by the bonus deadline.

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 book is reader-friendly and insightful, so it can be recommended also for Finnish-speaking students as support material. 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 finite-state 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 (with a somewhat different format than the last exams, however) (25.10.2003), in Finnish, ps/ pdf.

• Examination requirements are available.
• Previous exams of the T-79.1001 course

Feedback

Links

Some useful and fun links that are related to the course contents, but not part of the official course material.

• Simulators for finite state machines, pushdown automata, and Turing machines
• Robert M. Keller: More on Grammars and Their Languages - slides that cover many of the same topics as we do, but sometimes with a different approach
• SCIgen - An Automatic CS Paper Generator based on a context-free grammar
• Links to cellular automata applets: 1D cellular automata, Conway's Game of Life, self-replicating CA.
• Clay Mathematics Institute Millennium Prize Problems; note specifically the P vs. NP problem.