Theoretical Computer Science II (ACS II) - Overview

Lecturers: Prof. Dr. Malte Helmert and Dr. Andreas Karwath

Assistant: Dr. Gabriele Röger


Lectures: Wednesday, 9:15-11:00 and Thursday 9:15-10:00
Exercise sessions: Thursday, 10:15-11:00
Exam: Wednesday, March 3, 2010, 14:00-15:30


Lectures: Building 106, Room 00-007
Exercise sessions: Building 106, Room 00-007
Exam: Building 082, Room 00-006 ("Kinohörsaal")


Lectures are held in English, and the course material and exercise sheets are in English. Students may ask questions and submit exercise sheets in German or English.

Credit Points

6 ECTS points

Aims of the lecture

The participants should get a foundational knowledge of the theoretical aspects of computer science.

Contents of the lecture

This course will address theoretical aspects of computer science. It comprises the fundamental mathematical properties of computer hard and software. We will see what can be computed, and what cannot, and if it can be computed, how hard (efficient) it is to compute it. More specifically, the following topics will be included:
  • automata
  • formal languages
  • formal grammars
  • Turing machines
  • decidability
  • complexity theory
  • logic


The course is aimed at students of Applied Computer science in their 1st semester. Bachelor and master students of Computer Science cannot receive ECTS points in this course. Students of other degree programs can in certain cases participate upon prior agreement.


There will be a written exam after the lecture. Bonus points for the exam can be obtained by working on the exercise sheets and presenting at least one solution in an exercise session.