Theoretical Computer Science - Bridging Course
Material from Past Bridging Courses
Fabian Kuhn
Past exercise sheets
Winter Term 2016/2017
| Topic(s) | Exercise | Sample Solution | ||||
| Mathematical Preliminaries | Exercise 01 | Solution 01 | ||||
| DFA, NFA, Regular Languages | Exercise 02 | Solution 02 | ||||
| Regular expressions Non-regular languages |
Exercise 03 | Solution 03 | ||||
| Context Free Grammars I Context Free Grammars II |
Exercise 04 | Solution 04 | ||||
| Pushdown Automata Pumping Lemma for Context Free Grammars |
Exercise 05 | Solution 05 | ||||
| Turing Machines I Turing Machines II |
Exercise 06 | Solution 06 | ||||
| Decidability and decidable languages Decidability, mathematical backgrounds on cardinality Decidability and the halting problems |
Exercise 07 | Solution 07 | ||||
| Complexity I Complexity II |
Exercise 08 | Solution 08 | ||||
| Complexity III | Exercise 09 | Solution 09 | ||||
| Propositional Logic. Deduction/ Contraposition/Contradiction Theorems and Derivations | Exercise 10 | Solution 10 | ||||
|
Propositional Logic. Derivations, Soundness and Completeness of calculi Propositional Logic. Refutation-completeness and Resolution | Exercise 11 | Solution 11 | ||||
|
First Order Logic. Derivations First Order Logic. Satisfaction |
Exercise 12 | Solution 12 | ||||