Main Page

News

Lecture today starts at 14:30

Written on 04.12.24 by Markus Bläser

On very short notice, I have to attend an urgent meeting. The lecture will start at 14:30. We will finish at 16:00.

Exercise Sheet 5 - Delayed Correction

Written on 25.11.24 by Alexander Rogovskyy

Just a quick heads up: The 5th exercise sheet takes a WHILE longer to correct. We will thereFOR publish the results in the upcoming days.

Current Exercise Sheet & Reminder Room Change

Written on 20.11.24 by Alexander Rogovskyy

Pairing Function & Projections

Since the question came up a few times: The pairing function and the corresponding projections π_i for exercise E5.4 can be found in the script in Lemma 8.3.

(Note that you may not, of course, use the subsequent exercise 8.4 from the script since that's exactly our… Read more

Pairing Function & Projections

Since the question came up a few times: The pairing function and the corresponding projections π_i for exercise E5.4 can be found in the script in Lemma 8.3.

(Note that you may not, of course, use the subsequent exercise 8.4 from the script since that's exactly our task!)

LaTeX snippet for FOR and WHILE programs

As promised, we have uploaded a LaTeX snippet for FOR and WHILE programs. Of course, you do not have to use it and are free to use any other implementation / package (as long as it's readable ;) ).

Reminder: Room Change for Office Hour

This is just a quick reminder that tomorrow's (Thursday, 21st Nov) Office Hour will take place in a different room: E1.3, seminar room 014.

Room Change Next Week

Written on 15.11.24 by Alexander Rogovskyy

As announced in the lecture and the tutorials, room E1.3 015 will be closed next week (Nov 18th - 22nd). As a result, some tutorials and both office hours will take place in different locations.

Tutorial 6 (Jona Prinz)	E1.3, lecture hall 001
Tutorial 7 (Moritz… Read more

As announced in the lecture and the tutorials, room E1.3 015 will be closed next week (Nov 18th - 22nd). As a result, some tutorials and both office hours will take place in different locations.

Tutorial 6 (Jona Prinz)	E1.3, lecture hall 001
Tutorial 7 (Moritz Lohmann)	E2.5 (math lecture hall), lower floor, seminar room 4
Tutorial 8 (Adrian Scherhag)	E1.3, seminar room 107
Tutorial 9 (Jan Gindorf)	E1.3, seminar room 107
Office Hour on Wednesday 10:15	E1.3, seminar room 107
Office Hour on Thursday 14:15	E1.3, seminar room 014

Note that this is only valid next week. The following weeks, the rooms will be as usual.

As a quick follow-up to the current exercise sheet, we are planning to upload a small LaTeX template to help you write FOR and WHILE programs in the next few days.

Holiday & Third Sheet

Written on 01.11.24 by Alexander Rogovskyy

A quick reminder to everyone that today (Friday, November 1st) is a holiday in Saarland. Therefore, there will be no lecture today. However, the deadline for the second sheet remains today at 8am. To accomodate the request of some students, the third exercise sheet was released a bit earlier this time… Read more

We'll see you back next week at the tutorials on Tuesday and the lecture on Wednesday!

Plagiarism and other Reminders

Written on 26.10.24 by Alexander Rogovskyy

On Plagiarism

The first exercise sheet having been submitted, we would like to remind you of the policy regarding plagiarism. Naturally, you can and should work together in your submission group to solve the exercises (note that working together does not mean splitting the work!).

However,… Read more

On Plagiarism

However, copying work from another group as well as from other sources counts as plagiarism, and will be handled as such. The consequences can reach from the sheet being graded with 0 points to loss of rights to examination.

Therefore, it is in your best interest to earnestly work on the sheets within your group. If you have troubles with a particular exercise, you can use the office hours to receive help.

Regarding the Readability of Submissions

Those of you who prefer handwritten solutions are reminded that we do not accept photographed submissions. At the last sheet, we have received many solutions with very bad quality. In the future, we reserve the right to reject these solutions, even if they are correct content-wise.

Please scan your solutions with a scanner. To that end, you may use the scanners at the university or the Student’s Council scanner.

This Friday is a Holiday!

Last but not least: This Friday is a holiday in Saarland. Therefore, there will be no lecture on Friday. However, the exercise submission deadline is still unchanged on Friday.

First Exercise Sheet Submission Open

Written on 24.10.24 by Alexander Rogovskyy

The first exercise sheet can be submitteed now. You may submit the sheet for your group on your Personal Status page in the CMS. Only one person from each group needs to upload. The submission can be made until Friday, 25th October at 8:00 am.

Note that the submission is split into the three… Read more

Note that the submission is split into the three exercises. Therefore, you must upload each exercise separately in the respective upload fields. If you already have a single PDF file, you may split it using free tools such as pdfarranger.

If you have any technical problems with the upload, notify your tutor on time.

Tutorials Assigned & Reminders for next week

Written on 21.10.24 by Alexander Rogovskyy

The tutorials have been assigned. You can see which tutorial you were assigned to in your Personal Status page on the CMS. The first tutorial will be on the upcoming Tuesday.

Should this assigned tutorial slot for some reasons not work for you anymore, you can swap tutorials if you find a person in… Read more

The tutorials have been assigned. You can see which tutorial you were assigned to in your Personal Status page on the CMS. The first tutorial will be on the upcoming Tuesday.

Should this assigned tutorial slot for some reasons not work for you anymore, you can swap tutorials if you find a person in a different tutorial to swap with. In this case, write an email to the Assistant.

Reminder: Submission Groups

You have until the upcoming Wednesday (23rd October at 23:59) to register your submission groups in the CMS. In order to do that, you have to go to your Personal Status page on the CMS, where you will find buttons to join or create groups.

Groups can be up to 3 people and are independent of the assigned tutorial slots.

Still looking for a group?

Here are some places you can look for potential submission groups teammates:

Tutorial on Tuesday
Office Hour on Wednesday
in the Forum

Reminder: Exercise Sheet

The deadline for the first exercise sheet is on the upcoming Friday at 8am. The submission will open on Thursday, 24th October, at which point you will be able to upload your solutions on your Personal Status page.

Show all

Introduction to Theoretical Computer Science

Time & Date

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.

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 October 23rd, 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. Each group must write their own solution and must not copy the solution of another group!

The first exercise sheet is due October 25th, the submission will open on October 24th.

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 22nd. We are offering tutorials in both English and German. You have to register for your tutorials with your preferred tutorial language from the 15th of October until the 18th of October at 23:59 on this website.

Office Hours

Twice a week, always in room E1.3, seminar room 015:

Wednesdays 10:15-11:45
Thursdays 14:15-15:45
Starting on October 23rd and 24th respectively

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 written 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 2025, 14:00 - 17:00
Reexam: 26th of March 2025, 9:00 - 12: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. 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)

You may find these in the InfoMath library.