OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Prof. Tapio Elomaa

Fall 2012, periods I ja II

Lectures:
Weekly exercises: M.Sc. Teemu Heinimäki, Mon 8-10 TC210
Course exam: Mon Dec. 10, 2012

- News

- General Information

Course main page.

Mandatory prerequisites are a course on discrete mathematics (MAT-20601 Diskreetti matematiikka) and a course on algorithm analysis (OHJ-2156 Analysis of algorithms).

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 2012 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. 28 & 30 1 - 24 n/a Course Organization & Motivation
2 Sept. 4 & 6 25 - 55 Sept. 10 1.1, 1.2
3 Sept. 11 & 13 56 - 93 Sept. 17 1.3-1.4, 2.1
4 Sept. 18 & 20 94 - 133 Sept. 24 2.2-3.2
5 Sept. 25 & 27 134 - 171 Oct. 1 3.2-3.3 + unrestricted grammars
6 Oct. 2 & 4 172 - 207 Oct. 8 4 + universal TMs, 5.1
7 Oct. 9 & 11 208 - 226 Oct. 22 5.3
8 Oct. 23 227 - 243 Oct. 29 6.4
9 Oct. 30 & Nov. 1 244 - 275 Nov. 5 7.1-7.2
10 Nov. 6 & 8 276 - 304 Nov. 12 7.3-7.5
11 Nov. 13 & 15 305 - 339 Nov. 19 8
12 Nov. 20 340 - 362 Nov. 26 10.1
13 Nov. 27 & 29 363 - 390 -- 10.1-10.2
14 Dec. 4 391 - 400 -- --

- 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. 4, 2012 http://www.cs.tut.fi/~elomaa/