The class will take place every Wednesday from 4:15 pm to 6 pm in HG G26.1

Here you can find the material covered in class [DE] and some stuff to prepare for the exam.

This lecture gives an introduction to theoretical computer science, presenting the basic concepts and methods of computer science in its historical context. We present computer science as an interdisciplinary science which, on the one hand, investigates the border between the possible and the impossible and the quantitative laws of information processing, and, on the other hand, designs, analyzes, verifies, and implements computer systems.

The main topics of the lecture are:

• alphabets, words, languages, measuring the information content of words, representation of algorithmic tasks
• finite automata, regular and context-free grammars
• Turing machines and computability
• complexity theory and NP-completeness
• design of algorithms for hard problems

Week 12

We will cover the final chapter regarding “Grammatiken”.

Week 11

Here you can find a book covering some NP-complete problems. This week we are going to talk about polynomial reductions, NP-completeness and many graph problems. Here you can find a short recap incl. examples of EE- and R-Reducibility additional example for EE-Reductions. Here you can find this weeks slides.

Week 10

We are going to review Sheet 8, discuss the distinction between EE- and R-Reducibility, provide a concise introduction to space and time constructibility, and briefly touch on the topic of polynomial reducibility.

Week 9

Reducibility, in particular to EE and R reducibility.

Week 7/8

Introduction to reducibility, in particular to EE and R reducibility. We are also going to cover Rice’s theorem.

Week 6

Countability and some exercises to prepare for the midterm.

Week 5

Non-regularity, number of states in finite automata, NEA to EA transformation and more.

Week 4

Non-regularity

Week 3

Construction of finite automata, determine classes for every state and justification. In the end, we are going to introduce the concept of product automata.

Week 2

Kolmogorov complexity and counting arguments.

Week 1

Introduction to the course, alphabets, Kolmogorov complexity (will be covered in week 2). Here you can find an additional exercise (we are most likely not gonna be able to cover it). I will briefly talk about what you have to expect from Gradinaru in Numerical Methods as well - The style of the exam is most likely to change - focus much more on programming / implementing than past years.

Disclaimer: The information below are based on my experience and do not constitute information approved by Prof. Komm or Prof. Hromkovic.

Exam

You have two options to pass this course. The first and highly recommended way is to write two exams during the semester. The second option is take the exam during the session. However, this exam is much more difficult and it is much harder to receive good grades. The mid-term will be most likely take place around 5th - 10th November. The end-term will take place somewhere around December, 10th. The mid-term is typically easier and you should (Numerical Methods I’m looking at you) try as hard as possible to get a good grade since the topics covered in the second part are harder.

Since it is a pretty big class ~ around 500 students, they will try to make the exam as friendly as possible to correct. What does this mean for you? In each exam, there will be at least one memorization exercise (in form of gap texts) from class - basically free points. If you aim for > 5.5 you must get full points in this task. You should start as early as possible with memorizing the content from class.

Grading: You will have to receive at least 50% of the points (in each mid-term) for a 4.0 and 96% for a 6.0. In between, grades will be awarded linearly. Again, I cannot stress enough how important it is to get a good grade in the mid-term. If you can master the first exam well, you will have a good time studying for the second as there is little to no chance for you to fail and you are going to need time in the second half of the semester for SPCA and Numerical Methods.

Exam preparation

Good news: You can prepare very well for the exam! The style of the tasks is similar each year and the topics have been fairly consistent over the past ten years

Here you can download flash cards (Anki file) that I used when I was preparing for the mid- and end-term. Moreover, here you can find a brief overview of the topics that are (in my opinion) relevant for the exam. If you do not want to memorize the entire lecture as I did, I provide you with a weekly updated list that covers the most important definitions and theorems that you should be able to know by heart. You should try to understand the proofs from the lecture since the concepts covered in lecture are transferable to the exercise sheet. You can use this guide (Beweismuster) to get used to solve theoretical computer science exercises. Feel free to check out this from my friend Aaron Zeller too.

About this exercise class

My aim is to prepare you at best for the exam and the weekly exercise sheets. Thus, we will not really cover anything fancy beyond the content of the class and I will most likely not do cover last weeks exercise sheet (unless the solutions were too… creative). Every week, I am going to tell you which exercises are most important for the exam and which are pure diversion if you don’t like social life :)