Theoretical Foundations of Computer Science

"Lectures" (in principal Finnish) Mon & Tue 12-14 (till the end of April in Louhela): Wilhelmiina Hämäläinen (whamalai@cs.joensuu.fi)
Exercises - Wed 14-16 B180 (English): Roman Bednarik, Tue 16-18 TD106 (Finnish) : Anssi, Thu 14-16 B180 (Finnish): Wilhelmiina
The finnish page of TFCS is here.

Current

Final Results
Final Evaluation Criteria
Summary of the feedback (partly in Finnish):
2nd midterm - Fri 25.4. 2003, TD106, 12:00-15:00.
Midterm - Fri 14.3. 2003, the exam starts at 12:00. TD106
FAQ: Read this first before you ask the lecturer
How to keep your learning diary
The MIU system
Mailing list instructions Please, join to the list!
Notice! Lectures at Louhela Hall!
Exercises for the first session

Course description

The course gives an introduction to the theoretical foundations of computer science: how to model problems with formal languages and abstract machines. The course will be given by problem-based learning method, which means that subjects are learnt through solving problems. More about problem-based learning below. Some teaching sessions (small lectures) are given when needed in Finnish. Even if you can't any Finnish, You may still take this course. There will be an English exercise group and you may also solve the problems in an English speaking group in the lectures. This requires a little bit more self-studying, but that's anyway the point of problem-based learning. If you are interested in taking this course, please report the lecturer, so we can plan the best way to perform it! Tell also if you are taking Graphical Interfaces lectures, because they are in the same time as our lectures. In principle there are three ways to perform the course:

By taking a part problem solving and returning the learning diary weekly + exercises.
By performing the middle term exams + doing exercises.
By taking the final examination.

Preliminary contents

Current program

Rations: the mathematical concepts and proof methods required in the course introduction slides pdf
Introduction: Modelling problems, solvability, formal languages and their hierarchy.
Finite automata and regular languages Lecture notes. pdf Excursion: The applications of FA pdf
Excursion to L-systems pdf (week 5)
Pushdown automata and context-free languages
Excursion: about compilers, LL-systems and maybe something else... LL(1) grammars pdf
Turing machines and unristricted languages TM intro pdf
Excursion: context-sensitive languages - the problem of parsing the natural language
Universal language and universal Turing machines UTM pdf
Unsolvability Halting problem
Excursion: about the philosophy of artificial intelligence
Complexity theory
NP-complete problems

Problems

Problem 0 Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6
All problems

Exercises

Chapter 0: assignments 1, 5, 6, 7. Chapter 1: 1, 2
(the others are voluntary, still highly recommended to try (and present!))

All exercises
The materials concerning the exercises: Red Hood

Literature

There is not any officila course book, but instead a couple of recommendable literature. I will update a list about topics during the course weekly. In addition there will be Finnish lecture material ( a summary) + some additional material also in English. I recommend that you make your own learning material using the topic list as a sceleton!

Sipser, M. Introduction to the Theory of Computation. (Fun to read, a lot of interesting examples and tasks, but partly too narrow.)
Hopcroft, J.E., Motwani, R., Ulman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001. (Quite comprehensive.)
Kinber, E. & Smith, C. Theory of Computing. A Gentle Introduction. Prentice Hall, 2001. (Very kind introduction to the subject as said :)
Lewis, H.R. & Papadimitriou, C.H. Elements of the Theory of Computation, Second Edition, Prentice-Hall, 1998. (A classic, very good and comprehensive, but at least the 1. edition quite mathematical.)
Wood, D. Theory of Computation, Harper & Row, 1987.
Sudkamp, T.A. Languages and Machines. An Introduction to the Theory of Computer Science.