Written on 30.11.23 by Markus Bläser
As announced earlier, the lecture tomorrow (Dec 1) will take place in HS 1 of the math lecture hall (E2.5). It starts as usual at 8:30.
(Unfortunately, I used the wrong building number on the slides on Wednesday, it is E2.5 not E2.4!)
Written on 20.11.23 by Julian Dörfler
We would like to remind that you are not supposed to post significant parts of your solutions to exercise sheets in the forum before the deadline of said exercise sheet, since everybody can see them there. If your question can only be asked by giving specifics about your solution we kindly ask you to… Read more
We would like to remind that you are not supposed to post significant parts of your solutions to exercise sheets in the forum before the deadline of said exercise sheet, since everybody can see them there. If your question can only be asked by giving specifics about your solution we kindly ask you to pose those questions in the office hours instead.
Written on 08.11.23 by Julian Dörfler
Starting November 13th, we will be offering an additional office hour mondays 12:15-14:00 in room 0.08 in E1 7 (MMCI).
Written on 06.11.23 by Julian Dörfler
Due to current circumstances we would like to remind that plagiarism is obviously not allowed (this does include copying from previous years sample solutions and/or from ChatGPT). We reserve the right to give 0 points for the entire exercise sheet or even initiate further action.
Written on 31.10.23 by Julian Dörfler
There has been a slight mistake and the first exercise sheet accidentally has 17 total points instead of the promised 16 total points. To stay in line with the 16 points per exercise sheet the extra point will be considered bonus.
Written on 30.10.23 by Julian Dörfler
The tutorials have been assigned. You can see which tutorial you were assigned to in your Personal Status page. Should this assigned tutorial slot for some reasons not be possible for you anymore, you can swap tutorials if you have a swapping partner (i.e. a person wanting the swap the opposite… Read more
The tutorials have been assigned. You can see which tutorial you were assigned to in your Personal Status page. Should this assigned tutorial slot for some reasons not be possible for you anymore, you can swap tutorials if you have a swapping partner (i.e. a person wanting the swap the opposite direction) by having both of you send me an e-mail.
Introduction to Theoretical Computer Science
Time & Date
- Mi. 14:15-16:00 (E2 2 HS 001, Günter-Hotz-Hörsaal)
- Fr. 8:30-10:00 (E2 2 HS 001, Günter-Hotz-Hörsaal)
The lectures will be held in English.
Additionally the lectures will be recorded and put online afterwards, the links to the recordings can be found in the Materials category.
Exercise sheets & Tutorials
Every Friday we will release an exercise sheet. You have time until the next Friday at 8:00 to submit your solution via (this) CMS. You can work in groups of up to 3 students on the exercises. You need to register these groups until November 1st, 23:59, in CMS. The solutions are submitted as separate Pdf-files for each exercise, either digitally created, for example with LaTeX or LibreOffice, or as a high quality scan of a handwritten submission. The first exercise sheet is due November 3rd, the submission will open on November 2nd.
While the exercise sheets themselves will be in English, you are free to choose both German or English as the language for your submissions.
The exercise sheets and additional tutorial sheets will be discussed in the tutorials in week after the submission. For questions about the grading of your exercise sheets, please come to the Office Hours.
The tutorials are in person on Tuesdays and will start October 31st. We are offering tutorials in both English and German. You have to register for your tutorials with your preferred tutorial language from the 23rd of October until the 28th of October at 23:59 on this website.
- Mondays, starting 13th of November 12:15-14:00
- Thursdays, starting 2nd of November 14:15-16:00
To be admitted to the endterm and the reexam you need 50% of the regular points of all exercise sheets.
Your grade will be the better grade of:
For the exams you are allowed to bring a single(!) handwritten(!) DinA4-sheet, written on both sides. Photocopies and printouts are not allowed!
- Endterm: 20th of February 2024, 9:00 - 12:00 (raw time to complete the exam: 120 min)
- Reexam: 20th of March 2024, 9:00 - 12:00 (raw time to complete the exam: 120 min)
If for some urgent reasons you cannot attend the exams in person please contact us directly via email.
There are many good books on the topic of this lecture. Here is a selection:
- Michael Sipser, Introduction to the Theory of Computation, PWS
- John Hopcroft, Rajeev Motwani & Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson
- Harry Lewis & Christos Papadimitriou, Elements of the Theory of Computation, Prentice Hall
- Dexter Kozen, Automata and Computability, Springer
- Uwe Schöning, Theoretische Informatik - kurzgefasst, Spektrum (in German)