Introduction to Theoretical Computer Science

Lectures:

• Wed. 14:15-16:00 (E2 2, Günter-Hotz-Hörsaal)
• Fri.     8:30-10:00 (E2 2, Günter-Hotz-Hörsaal)

The lectures will be held in English.

The lectures will not be recorded, so we would like to invite all participants to join us in person.

Exercise Sheets

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 Tuesday, October 21st, 23:59, in CMS.

The solutions are submitted as separate PDF-files for each task; do not merge the solutions for different tasks together. One person from each group has to upload the solution (it does not have to be the same person for all tasks).

Every PDF submission for a task must be either

• digitally created, for example with LaTeX or LibreOffice or Typst, or
• a high quality scan of a handwritten submission. 

In particular, phone "scans" more often than not turn out to be badly readable, blurry or misaligned. In these cases, we reserve the right to deduce points. The same holds for unreadable handwritten submissions.

While the exercise sheets themselves will be in English, you are free to choose both German or English as the language for your submissions.

For questions about the grading of your exercise sheets, please ask your tutor or come to the Office Hours.

 

Group Work Policy

What groups are for:

• Arriving at solutions by discussing the tasks together.
• Saving time of writing down (note: not solving, but just writing down) the solutions that you have arrived at together.

What groups are not for:

• Splitting up the work. Everyone solves one exercise.
• "Rainer T.  knows everything much better than us anyway, so might as well let him do all the tasks. Our chances of getting the admission will be higher this way". In other words: one person does all.

In particular, we expect all group members to fully understand and be able to explain all submitted solutions.

But what if person X did not contribute to one particular exercise?

Then you may explicitly write that down in the submission - the respective person would be free from any responsibility for said exercise, but will also not receive points for it. 

But what if person X repeatedly does very little and refuses to participate in or contribute to group work?

Then the group is dysfunctional. You may (and probably should) contact the assistants so we can remove said person from the group.

 

Plagiarism Policy

...aka: what about ChatGPT & co.?

First of all, we need to differentiate between

1. Using ChatGPT to study and understand the concepts and
2. Using ChatGPT to solve the exercises given to you

Case 1 is obviously allowed and does not require any special indication. It is a perfectly valid way to learn, not much different from doing regular research on the internet. Therefore, in what follows, we will mainly concern ourselves with case 2.

Case 2 means that you have used an external source for a (parts of a) solution. You should clearly indicate what source you used for what part of the solution on the same submission (same PDF file) as the task.

If you do not state your source, it will count as plagiarism.

If you state your source, it will not be plagiarism. We will grade the solution, but upon the first (no matter how small) mistake we will stop the grading and award that particular exercise 0 points. We will also not put in extra effort to give detailed feedback (why would we be giving feedback to ChatGPT?)

Note that while we were mostly mentioning ChatGPT, the same holds for other external sources as well.

In addition:

• Any materials from this year's iteration of the lecture can be used and using them is never counted as plagiarism.
• Copying any part of a solution of another group always counts as plagiarism.

Tutorials

The tutorials are in person on Mondays and will start October 20th. We are offering tutorials in both English and German. You have to register for your tutorials with your preferred tutorial language until October 18th at 23:59 on this website.

Office Hours

• Tuesdays, 16:15, E1.3 SR013
• Thursdays 14:15, E1.3 SR013

Exam Admission

There will be a midterm on December 2nd from 16:00-19:00. Attendance is optional, but the midterm will grant points that will go towards the exam admission, similar to exercise sheets. 

To be admitted to the endterm and the reexam you need at least 50% of the sum of

• the regular points of all exercise sheets and
• the points of the midterm.

Your grade will be the better grade of:

• Endterm
• Reexam

Exams

For the written exams you are allowed to bring a single(!) handwritten(!) DinA4-sheet, written on both sides. Photocopies and printouts are not allowed!

• Endterm: 11th February 2026, 09:00 - 12:00
• Reexam:  1st April 2026, 10:00 - 14:00

The raw time to complete the exam will be at least 120 minutes.

 

Literature

There are many good books on the topic of this lecture. You find a selection below.  The first book in this list is probably closest to the course.

• John Hopcroft, Rajeev Motwani & Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson
• Michael Sipser, Introduction to the Theory of Computation, PWS
• 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)

You may find these in the InfoMath library.

 

Lecture Recordings

We will try to make recordings of the lecture available, but with no guarantees (the attempt for the first lecture failed in that it only recorded sound).

Lecture 2    (set theory, countability, etc.)      passwd:        8U$6wxFM