OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Prof. Tapio Elomaa, Asst.prof. Henri Hansen, Asst. Timo Aho

Fall 2011, periods I ja II

Lectures:
Weekly exercises: M.Sc. Teemu Heinimäki, Fri 10-12 TC210
Course exam: Thu Dec. 15, 2011, 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 2011 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 1 - 11 n/a Course Organization
2 Sept. 6 & 8 12 - 35 n/a 0, 1.1
3 Sept. 13 & 15 36 - 73 Sept. 23 1.2-1.3
4 Sept. 20 & 22 74 - 104 Sept. 30 1.4-2.1
5 Sept. 27 & 29 105 - 135 Oct. 10 2.2-3.2
6 Oct. 4 136 - 151 Oct. 14 3.3 + unrestricted grammars
7 Oct. 11 & 13 152 - 184 Oct. 28 4 + universal TMs
8 Oct. 25 & 27 185 - 218 Nov. 4 5.1, 5.3
9 Nov. 1 & 3 219 - 242 Nov. 11 5.3, 6.4
10 Nov. 8 & 10 243 - 269 Nov. 18 7.1-7.2
11 Nov. 15 & 17 270 - 297 Nov. 26 7.3-7.5
12 Nov. 22 & 24 298 - 323 Dec. 2 8
13 Nov. 29 & Dec. 1 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, 2011 http://www.cs.tut.fi/~elomaa/