Introduction to Theoretical Computer Science

Registration and Information for the Endterm Exam

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 96 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 Alexander Rogvoskyy via E-Mail (see team page) until the 13th of February.
• You are allowed to bring a single(!) handwritten(!) DIN A4-sheet, written on both sides to the exam. Photocopies and printouts are not allowed!
• Relevant for both exams are chapters 1 to 26 (inclusive) in the lecture notes (excluding bonus chapters) and all exercises from exercise sheets 1 to 13 (inclusive) and tutorial sheets 1 to 14 (inclusive).  Exercises marked with at least one star are excluded.
• Further information for the exam will follow closer to the exam.

Office Hours and Mock Exam

The last regular office hour will be on Thursday, 6th February.

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

• Two "last minute" office hours
  • 14th February 12:00-16:00, E1.3 seminar room 014
  • 19th February 12:00-16:00, E1.3 seminar room 014
• A mock exam with a consecutive discussion of the solutions.
  • 12th February  starting at 12:30 in the Günther-Hotz lecture hall (GHH)
  • 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 10th of February if you plan to participate in the mock exam so we know how many copies we have to print.

To reinforce the topics around NP/NP-completeness a bit more, we will be offering an additional special tutorial next Wednesday (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).

Place: E2.5 (Math lecture hall building), HS I
Time: Wednesday, January 29th, starting at 16:15

Hi everyone!

The last week before the long-awaited Winter Holidays is over. The TCS team wishes everyone great holidays and an even greater start in the new upcoming year 2025!

And finally, a small announcement, regarding one of the probably most asked questions that we received: We will have 13 exercise sheets in total!

Have fun with the Winter Sheet; we'll see you again at the tutorials on 7th January!

- Your TCS Team

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.

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.

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.

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 (note that the first uploaded version contained outdated submission date). It is due on Friday, November 8th, at 8am.

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

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

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

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.