News

Endterm results and exam inspection

Written on 22.02.24 by Julian Dörfler

  • The endterm has been corrected and results are now visible on your Personal Status page.
  • The exam inspection will take place on the 1st of March from 13:00 to 15:00 in E1 3 HS002. You have to register until the 28th of February 15:00 on your Personal Status page if you want to participate in the… Read more
  • The endterm has been corrected and results are now visible on your Personal Status page.
  • The exam inspection will take place on the 1st of March from 13:00 to 15:00 in E1 3 HS002. You have to register until the 28th of February 15:00 on your Personal Status page if you want to participate in the exam inspection. Please reserve the entire period from 13:00 to 15:00 for this exam inspection, once the registration is closed we will assign you a specific timeslot for your own exam inspection.

Information for the endterm exam

Written on 18.02.24 by Julian Dörfler

Please note the following information:

  • The endterm exam will take place on the 20th of February 2024, approximately from 9:00 to 11:00
  • In order to guarantee a smooth process, we ask you to be there at 8:45 at the latest.
  • You can see which lecture hall you are writing the exam in on your… Read more

Please note the following information:

  • The endterm exam will take place on the 20th of February 2024, approximately from 9:00 to 11:00
  • In order to guarantee a smooth process, we ask you to be there at 8:45 at the latest.
  • You can see which lecture hall you are writing the exam in on your Personal Status page.
  • Please bring your student ID, as well as an official photo ID (ID card/passport/...).
  • Please bring a blue or black non-erasable pen, for example a ballpoint pen, but not pencils.
  • You are allowed to bring a single(!) handwritten(!) DinA4-sheet, written on both sides to the exam. Photocopies and printouts are not allowed!

Registration and Information for the Endterm Exam

Written on 06.02.24 by Julian Dörfler

Please note the following information:

  • All exercise sheets are now corrected and the points are visible on your Personal Status page.
  • To be admitted to the exam you need at least 91 points (including bonus points).
  • Please don't forget to register in HISPOS/VIPA/etc. Note that the deadlines… Read more

Please note the following information:

  • All exercise sheets are now corrected and the points are visible on your Personal Status page.
  • To be admitted to the exam you need at least 91 points (including bonus points).
  • Please don't forget to register in HISPOS/VIPA/etc. Note that the deadlines for this may vary. Also note that since summer semester 2019 there is no possibility of late registration at all. We will regularly import the HISPOS registration into the CMS. If you are unable to use the HISPOS due to your course of study, you have to register with Julian Dörfler via E-Mail (see team page) until the 13th of February.
  • You are allowed to bring a single(!) handwritten(!) DinA4-sheet, written on both sides to the exam. Photocopies and printouts are not allowed!
  • Relevant for both exams are chapters 1 to 28 in the lecture notes (excluding bonus chapters) and all exercises from exercise sheets 1 to 12 and tutorial sheets 1 to 14 (excluding exercises marked with at least one star).
  • Further information for the exam will follow closer to the exam.

Office Hours and Mock Exam

Written on 30.01.24 by Julian Dörfler

The last regular office hour is on the 1st of February.

However for your preparations for the exams we are offering the following:

  • Two last minute office hours, on the 13th and 19th of February from 12:00 to 16:00 each in room SR016 in E1 3.
  • A mock exam on the 15th of February, starting at… Read more

The last regular office hour is on the 1st of February.

However for your preparations for the exams we are offering the following:

  • Two last minute office hours, on the 13th and 19th of February from 12:00 to 16:00 each in room SR016 in E1 3.
  • A mock exam on the 15th of February, starting at 12:30 in E1 3 HS 002 with a consecutive discussion of the solutions. This discussion will not be recorded. Please bring your own paper to write on for the mock exam. Furthermore please register in the CMS until the 13th of February if you plan to participate in the mock exam so we know how many copies we have to print.
     

Special Tutorial, January 29th

Written on 23.01.24 by Julian Dörfler

To reinforce the topics around NP/NP-completeness a bit more, we will be offering an additional special tutorial next Monday (Jan 29th). This tutorial is planned to be a crash-course for problems in NP, polynomial-time reductions, etc. We highly recommend attending there, if you still have any trouble… Read more

To reinforce the topics around NP/NP-completeness a bit more, we will be offering an additional special tutorial next Monday (Jan 29th). This tutorial is planned to be a crash-course for problems in NP, polynomial-time reductions, etc. We highly recommend attending there, if you still have any trouble with these concepts.

We'll provide you with explanations and have inbetween exercise phases, where you'll be working on another tutorial sheet (which will be different from the regular tutorial sheet).

This tutorial will take place in E1.3, HS 002. It starts at 16:15.
 

Office Hour today, January 18th

Written on 18.01.24 by Julian Dörfler

Even though the busses aren't driving today, the office hour will take place as usual.

Lecture tomorrow, Wed Jan 17, will be online

Written on 16.01.24 by Markus Bläser

I guess you got all the mails and warnings... due to the danger of ice, the lecture tomorrow will be conducted online (and only online!) via Zoom. You can find the link in cms on the materials page at the bottom under "7. Links". As usual, we will make recordings available afterwards. Take care.

No Office Hour on Thursday

Written on 08.01.24 by Julian Dörfler

Unfortunately, due to a lack of available rooms, we have to cancel the office hour on the 11th of January.

Change of Room!

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!)

Posting Solutions in the Forum

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.

Additional Office Hour

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).

Plagiarism

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.

Points on the first assignment sheet

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.

Assignment to the tutorials

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.

Show all

Introduction to Theoretical Computer Science

 

Time & Date

Lectures:

  • 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.
 

Office Hours

Twice a week, always in room 0.08 in E1 7 (MMCI):
  • Mondays, starting 13th of November 12:15-14:00
  • Thursdays, starting 2nd of November 14:15-16:00

Grading

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:

  • Endterm
  • Reexam

Exams

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.

 

Literature

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)

 

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.