Institute for Computer Languages

Compilers and Languages Group

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

Regular ATCS lectures start | 2012-10-11, 12:15 - 14:00 EI 5 Hochenegg HS Handouts are online (see below). |

First exercise session: | 2012-10-17, 11:15-12:00EI 4 Reithoffer HS Homeworks are online (see below). |

Final exam |
February 21, 10am-1pm
Library of E185.1 Argentinierstr. 8, 4th floor |

The course is assigned to the master curricula:

- 066 937 Software Engineering & Internet Computing
- 066 931 Computational Intelligence
- 066 938 Computer Engineering

Please register to the course via the

CompLang registration system (this link).

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 |

We will maintain the following mailing list:

atcs12 at complang dot tuwien dot ac dot at

starting from October 11th, 2012.

- Course type: VU (lecture with exercises)
- Course hours: 2 semester hours
- Lecture: 2 x 45 minutes /week
- Exercise: 1 x 45 minutes / week
- Course credits: 3 ETCS
- Course language: English

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.

- Can a given problem be solved by computation?
- How efficiently can a given problem be solved by computation?

- Models of computation (
*Automata Theory*)- Finite automata
- Pushdown automata
- Turing machines

- What can we compute? (
*Computability Theory*) - How efficiently can we compute? (
*Complexity Theory*)

- Michael Sipser,
*Introduction to the Theory of Computation*. Second (International) Edition, Thomson Course Technology, 2005. ISBN 0-619-21764-2. Web-site.

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.

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.

- Computational models:
- Finite state automata and regular languages;
- Pushdown automata and context-free grammars;
- Turing machine;

- The Chomsky hierarchy;
- From problems to languages;
- Undecidability and reductions;
- Decision problems about languages;
- Complexity classes (P and NP);
- Polynomial hierarchy.

**Lecture 1**(2012-10-04, introduction):- Motivation and course outline

**Lecture 2**(2012-10-11):

**Lecture 3**(2012-10-18):- Nondeterminism in finite automata (Handout 3)

**Lecture 4**(2012-10-25):

**Lecture 5**(2012-11-08):- Push-down automata and context-free languages (Handout 6)

**Lecture 6**(2012-11-22):- Pumping lemma for context-free languages (Handout 7)

**Lecture 7**(2012-11-29):

**Lecture 8**(2012-12-06):- Nondeterminism in Turing Machines (Handout 10)
- Closure properties of Turing Machines

**Lecture 9**(2012-12-13):- Undecidability in Turing Machines (Handout 11)

**Lecture 10**(2012-12-20):- Mapping reductions and undecidability in Turing machines

**Lecture 11**(2013-01-10):- Complexity classes, P vs NP (Handout 12)

**Lecture 12**(2013-01-17):- NP-completeness (Handout 13)
- Examples of NP-complete problems (3SAT, HAMPATH.pdf, CLIQUE, SubsetSum)

**Lecture 13**(2013-01-24):- Final course revision