Algorithms and Complexity

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

Past exams

Winter Term 2016/2017

Exam from Winter Term 2016/2017

Solution from Winter Term 2016/2017

Summer Term 2016

Exam from Summer Term 2016

Solution from Summer Term 2016