OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Prof. Tapio Elomaa

Fall 2010, periods I ja II

Lectures:
Weekly exercises: M.Sc. Teemu Heinimäki Fri 8-10 TC210
Course exam: Wed Dec. 15, 2010, 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.

- Lectures

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

WeekDatesSlidesExercises Chapters in the Book
1 Aug. 31 & Sept. 2 1 - 32 Sept. 8 0, 1.1
2 Sept. 7 & 9 33 - 59 Sept. 15 1.1-1.2
3 Sept. 14 & 16 60 - 79 Sept. 22 1.3-1.4
4 Sept. 21 & 23 81 - 108 Oct. 1 2.1-2.2
5 Sept. 28 & 30 109 - 134 Oct. 8 3.1-3.2
6 Oct. 5 & 7 135 - 163 Oct. 15 3.3 + unrestricted grammars
7 Oct. 12 & 14 164 - 190 Oct. 29 4 + universal TMs
8 Oct. 26 & 28 191 - 225 Nov. 5 5.1, 5.3
9 Nov. 2 & 4 226 - 242 Nov. 12 6.4
10 Nov. 9 & 11 243 - 268 Nov. 19 7.1-7.2
11 Nov. 16 & 18 270 - 297 Nov. 26 7.3-7.5
12 Nov. 23 & 25 298 - 323 Dec. 3 8
13 Nov. 30 & Dec. 2 324 - 370 -- 10.1-10.2

- Weekly Exercises

- Contents

  1. Introduction
  2. Recap
  3. Context-Free Grammars
  4. Universal Models of Computation
  5. Computability Theory
  6. Reducibility
  7. Advanced Topics in Computability Theory
  8. Time Complexity
  9. Space Complexity
  10. Approximation
  11. 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. 2, 2010 http://www.cs.tut.fi/~elomaa/