##
Theoretical Computer Science - Bridging Course

Graduate Course - Summer Term 2021

Fabian Kuhn

## Course description

The aim of the course is to provide basic knowledge of theoretical computer science to computer science M.Sc. students who do not yet have this necessary background (e.g., because of a different major during their undergraduate studies). The course introduces the (mathematical) foundations of theoretical computer science. We will see what can be computed and how efficiently, as well as what cannot. More specifically, the following topics will be included:

- Automata
- Formal languages
- Formal grammars
- Turing machines
- Decidability
- Complexity theory
- Logic

**Course Format**

The course is based on existing recordings provided
by Diego
Tipaldi combined with weekly interactive ** online** exercise lessons. This will prepare the participants for the final exam. The online lectures are given in the table further below.

**Schedule**

In conjunction with the the recorded lecture we offer weekly online exercise lessons.
The exercise lessons will take place **online** every **Wednesday** at **12:15 - 14:00** *(date was moved)* via the conference system Zoom.
The link on how to access the Zoom meeting is found in the access data section below. Also a forum will be set up on Zulip for questions about the lecture and the exercises. Further details will be given shortly.

**Announcement**

It was requested to move the date of the exercise lesson to Wednesday 12:15 pm - 2 pm. So we will move the exercise session unless there is a objection by someone (so far no one objected on Zulip). Please notify us in case this changed date does not work for you. Otherwise we will meet on Wednesday.

**Data Access**

The link on how to access the Zoom meetings is available here, which is only visible from within the university network (i.e., use VPN to access the page from home or access the internet via the university eduroam).

## Course Material

The course is based on existing recordings provided by Diego Tipaldi

Topic |
Slides |
Recordings |

Mathematical Preliminaries | MP4 (44:30) | |

DFA, NFA, Regular Languages | MP4 (1:14:04) | |

Closure of Regular Languages | ||

Regular expressions | MP4 (1:37:55) | |

Non-regular languages | MP4 (22:12) | |

Context Free Grammars I | MP4 (1:34:09) | |

Context Free Grammars II | MP4 (42:00) | |

Pushdown Automata | MP4 (1:11:18) | |

Pumping Lemma for Context Free Grammars | MP4 (1:29:51) | |

Turing Machines I | MP4 (52:31) | |

Turing Machines II | MP4 (1:23:03) | |

Decidability and decidable languages | MP4 (52:54) | |

Decidability, Cardinality, Cantor's diagonal argument | MP4 (1:15:40) | |

Decidability and the Halting Problems | MP4 (12:50) | |

Complexity I | MP4 (1:28:51) | |

Complexity II | MP4 (1:34:27) | |

Complexity III | MP4 (1:28:08) | |

Propositional Logic and basic definitions, CNF/DNF, logical entailment. | MP4 (37:11) | |

Propositional Logic, Deduction/Contraposition/Contradiction Theorems | MP4 (1:00:14) | |

Propositional Logic, Derivations, Soundness and Completeness of calculi | MP4 (53:16) | |

Propositional Logic, Refutation-completeness and Resolution | MP4 (04:16) | |

First Order Logic, Derivations | MP4 (46:47) | |

First Order Logic, Satisfaction, Closed Formulae, Overview on Normal Forms | MP4 (1:39:04) |

## Exercise Material

You will be provided with an exercise sheet every week to practice the lecture material in this section. The solutions will be discussed in the exercise lessons the week after. It is not mandatory to submit solutions. However, in case you wish to get feedback on your written solutions, you have to hand them in by the given deadlines. All submissions must be in, or converted to pdf format.

We recommend to prepare your solutions with Latex for best readability. Solutions prepared with Word or similar text editors or scans or photos of handwritten solutions in pdf format are ok, but must be well readable. Send your solutions via email to salwa.faour@cs.uni-freiburg.de (even exercise numbers) or philipp.schneider@cs.uni-freiburg.de (odd exercise numbers) by the given deadlines.

Exercise |
Topic |
Assigned |
Due (12 pm) |
Solution |
||

Exercise 01 | Mathematical Preliminaries | 20.04.2021 | 27.04.2021 | Solution 01 | ||

Exercise 02 | DFA, NFA, Regular Languages | 28.04.2021 | 05.05.2021 | Solution 02 | ||

Exercise 03 | Regular Expressions, Pumping Lemma | 05.05.2021 | 12.05.2021 | Solution 03 | ||

Exercise 04 | Context-Free Grammars, Pushdown Automata | 12.05.2021 | 19.05.2021 | Solution 04 | ||

Exercise 05 | Turing Machines | 19.05.2021 | 02.06.2021 | Solution 05 | ||

Exercise 06 | Decidability | 02.06.2021 | 09.06.2021 | Solution 06 | ||

Exercise 07 | Polynomial Time Decidability | 09.06.2021 | 16.06.2021 | Solution 07 | ||

Exercise 08 | Class NP & Intro to NP-completeness | 16.06.2021 | 23.06.2021 | Solution 08 | ||

Exercise 09 | More NP-complete Problems & Overview | 23.06.2021 | 30.06.2021 | Solution 09 | ||

Exercise 10 | Propositional Logic, CNF, DNF | 30.06.2021 | 07.07.2021 | Solution 10 | ||

Exercise 11 | Correct & Complete Calculi, Resolution | 07.07.2021 | 14.07.2021 | Solution 11 | ||

Exercise 12 | Predicate Logic | 14.07.2021 | 21.07.2021 | Solution 12 |

## Additional Material

**Lecture notes of a previous edition of this course.**

Covers everything except the parts on propositional and first order logic.

**Text Books:**