## News

## TUE-torial once more
As Monday is a holiday, we will have the tutorial on Tuesday again this week from 8:30. |

## Tutorial on TUESDAY
I am out of town on Monday. We will have the tutorial on Tuesday instead (only for this week) from 8:30 a.m. Hope that works out for most of you. If you are not able to attend and have questions regarding the assignment, feel free to drop by any time at my office room E1 4 - 327. |

## Assignment 3
Assignment 3 is now uploaded. |

## Regular Lecture tomorrow
There will be a lecture tomorrow at the usual time (12:15) and place (HS 001) given by Harry. I hope to be back on stage on Thursday. |

## First assignment
As you already saw, we uploaded a first assignment. You can form teams in cms until Tuesday. The assignment submission will open afterwards and is then open until Thursday evening. We will have a small tutorial on Monday Apr 29 in SR 014 in E.1.3 starting at 8:30. I am still ill, so we did not prepare… Read more As you already saw, we uploaded a first assignment. You can form teams in cms until Tuesday. The assignment submission will open afterwards and is then open until Thursday evening. We will have a small tutorial on Monday Apr 29 in SR 014 in E.1.3 starting at 8:30. I am still ill, so we did not prepare anything. But you can ask questions. If you plan to attend on Monday, please drop Sagnik an email so that he does have to get up for 0 persons. |

## No lecture tomorrow
I am still sick. There will be no lecture tomorrow. I will upload another old video instead. |

## No lecture today
Unfortunately, I got sick overnight. There will be no lecture today. I uploaded two videos. Please watch the proof of the Immerman Szelepcsényi Theorem (second half of the first and first half of the second video). Sorry for the mess. I will keep you posted about the Thursday lecture. |

## Complexity Theory

Complexity theory is the science of classifying problems with respect to their usage of resources. Ideally, we would like to prove statements of the form “There is an algorithm with running time O(t(n)) for some problem P and every algorithm solving P has to use at least Ω(t(n)) time”. But as we all know, we do not live in an ideal world

This lecture builds upon "Grundzüge der Theoretischen Informatik/Introduction to Theoretical Computer Science".

### Time and Date:

- Tuesday, 12:15 - 14:00, E1.3 HS001
- Thursday, 10:15 - 12:00, E1.3 HS001
- First lecture:
**Tuesday, April 16**

We plan to record the lectures.

### Tutorials:

- Mon 8:30-10:00. Room SR 014. The first tutorial will be
**April 29!**

### Assignments:

There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments. You can submit assignments in groups of up to three persons.

### Exams:

There will be oral exams at the end of the semester.

The exams can be at any time between the last week of the lecture period and end of October (provided that I am available). I will be on holiday from July 29 to August 9.

### Prerequisites:

"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NP-completeness) is highly recommended.

### Literature:

There are many good books an the topic. Here is a selection:

- Sanjev Arora and Boaz Barak,
**Computational Complexity - A Modern Approach**, Cambridge University Press. - Oded Goldreich,
**Computational Complexity - A Conceptual Perspective**, Cambridge University Press. - Uwe Schöning,
**Gems of Theoretical Computer Science**, Springer. - Rüdiger Reischuk,
**Komplexitätstheorie (Band 1)**, Teubner.