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) |
Additional Material
Lecture notes of a previous edition of this course.
Covers everything except the parts on propositional and first order logic.
Text Books: