OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Prof. Tapio Elomaa

Fall 2009, periods I ja II

Lectures:
Weekly exercises: Ph.D. Jussi Kujala
Course exam: Tue Dec. 15, 2009, 9 - 12 AM

- News

- General Information

Course main page.

Mandatory prerequisites are a course on discrete mathematics (MAT-20600 Diskreetti matematiikka) and a course on algorithm analysis (OHJ-2150 Algoritmien analyysi).

The course can be included in post-graduate studies. It is compulsory course in the advanced studies within computer science.

The course offers an introduction to the fundamental possibilities of programming and computation - which problems can be solved in principle by computing and, additionally, which problems can be solved efficiently. What can be done if the problem needing solution cannot be solved efficiently using computers. Lisäksi pyritään vetämään näiden tulosten yhteyksiä käytännön ohjelmistotyöhön.

- Lectures

The lectures of Fall 2009 are based on the book Course exams are based on lectures and not solely on the lecture slides.

WeekDatesSlidesExercises Chapters in the Book
1 Sept. 8 & 10 PDF -- 0, 1.1
2 Sept. 15 & 17 PDF Sept. 24 1.1-1.2
3 Sept. 22 & 24 PDF Oct. 1 1.3-1.4
4 Sept. 29 & Oct. 1 PDF Oct. 8 2.1
5 Oct. 6 & 8 PDF Oct. 15 2.2, 3.1-3.2
6 Oct. 13 & 15 PDF Oct. 27 3.3 + unrestricted grammars
7 Oct. 27 & 29 PDF Nov. 3 4 + universal TMs
8 Nov. 3 & 5 PDF Nov. 10 5.1, 5.3
9 Nov. 10 & 12 PDF Nov. 17 7.1-7.2
10 Nov. 17 & 19 PDF Nov. 24 7.3-7.5
11 Nov. 24 & 26 PDF Dec. 1 8
12 Dec. 1 & 3 PDF 10.1

- Weekly Exercises

Weekly exercises yield extra points.
Attending the weekly exercises and solving the exercises independently is an almost necessary prerequisite for passing the course.

- Contents

  1. Introduction
  2. Recap
  3. Context-Free Grammars
  4. Universal Models of Computation
  5. Computability Theory
  6. Reducibility
  7. Time Complexity
  8. Space Complexity
  9. Approximation
  10. Randomized Algorithms

- Literature

Almost any text book on this topic contains most of the material covered in the lectures. Such books are e.g.:

- Links


Dec. 3, 2009 http://www.cs.tut.fi/~elomaa/