Institute for Computer Languages
Compilers and Languages Group

Advanced Topics in Theoretical Computer Science (Fall 2012)

Course code: 185.A63

Course acronym: ATCS

Note: This course is the new version of the Advanced Theoretical Computer Science course (185.349) from Fall 2010 and Fall 2011.

Course news and calendar:

Course type: VU, 3 ETCS

The course is assigned to the master curricula:

Course Schedule


Please register to the course via the
CompLang registration system (this link).


Thursdays, 12:15-14:00, EI 5 Hochenegg HS

Exercise Sessions:

Wednesdays, 11:15-12:00, EI 4 Reithoffer HS
Schedule of Exercise Sessions:
Exercise Session Number Date
Exercise Session 1 October 17
Exercise Session 2 November 7
Exercise Session 3 November 28
Exercise Session 4 December 12
Exercise Session 5 January 23

The staff is always glad to help you. Whenever you get lost, desire help, or just want to talk, please contact us - don't let yourself fall behind! If you can't come to our office hours, send us email to set up an individual appointment.


Number Problem set Handed out on Due on Solution
1 Homework 1 October 11 October 17 Solution 1
2 Homework 2 October 18 October 25 Solution 2
3 Homework 3 October 25 November 8 Solution 3
4 Homework 4 November 8 November 22 Solution 4
5 Homework 5 November 22 December 6 Solution 5
Midterm Revision December 10
6 Homework 6 December 13 December 20 Solution 6
7 Homework 7 December 20 January 10 Solution 7
8 Homework 8 January 17 January 24 Solution 8

Mailing List

We will maintain the following mailing list:
atcs12 at complang dot tuwien dot ac dot at
starting from October 11th, 2012.

Course Information

Course type


The course goes into greater depth than the Theoretical Computer Science course, from the bachelor studies.

Students are expected to have attended or be familiar with the topics covered by the lectures Discrete Mathematics, Algorithms and Theoretical Computer Science.


The course presents some of the most fundamental results in theoretical computer science. These results attempt to answer, in a precise mathematical sense, the following two questions: Thus, we focus on problems rather than on specific algorithms for solving problems. To answer both questions mathematically, we need to start by formalizing the notion of "computer" or "machine". So the course outline breaks naturally into three parts:


The course material is built upon the following book:

Lecture notes:

Lecture notes will be distributed online, at the beginning of each lecture.

Exercise Sessions:

Participation in exercise sessions is optional but advisable. During exercise sessions, previous and new homework problems will be discussed, and examples will be presented which aid in the understanding of the lecture material. Exercise sessions are also an excellent time to ask questions about the course material and about homework problems.

Exercise sessions are not the place to work out homework solutions!


A problem set is handed out at the end of each lecture, and is due at the beginning of the lecture on the following week.
If you cannot attend a exercise session, you may turn in your homework to our office or via email, before noon on the due date.

Model solutions are handed out and discussed during the exercise sessions. The checked problem sets will be returned a week later, at the beginning of the lecture. Problem sets that are not picked up in the lectures will be kept in our office.

There will be a total of 8 problem sets. Your best 4 performances on the 8 homeworks will count towards your course grade.

If you have questions about course material or homework problems, please talk to us as soon as possible. We are more than happy to help you, during office hours and at any other time.

Grading and Exam:

Your course grade will be based on your homework and final exam scores.

Homeworks will count for 40% of the course grade. The final exam will count for 60% of the course grade.

The final exam will take place during the regularly scheduled exam period. You will be allowed to bring one A4-size sheet of hand-written notes to the exam. No other material is allowed.

Course Topics:

The list of topics covered by the course is below:

Course Outline:

Laura Kovács
Faculty of Informatics
Vienna University of Technology
top | HTML 4.01 | last update: 2015-02-20 (Webmaster)