Department of Computer Science

PD Dr Henning Bordihn

Foundations of Computer Science (FM 2), Winter Term 2019/20

Lecturer:   PD Dr. Henning Bordihn, Dr. Berfin Aktas
Program: Master of Cognitive Systems
SWS: 4
Credits: 6
Module: FM 2


Form: Class   Time: Thursday,   16:15-17:45,   Form: Lab   Time: Monday,   10:15-11:45,   02.05.103   First Meeting: 17.10.19


The course consists of two (almost independent) parts.

Content of Algorithms, Complexity, Automata, Formal Languages

This is a reading course. Video lectures provided in the internet can be used in addition. Details are given in the slides of the Introduction.

The course covers two fundamental topics:

1. Fundamentals of Computing
2. Theory of Computation

Slides and Assignments



Assignment 1a: Algorithms and their complexity I

Assignment 1b: Algorithms and their complexity II

Assignment 2: Finite state automata

Assignment 3: Regular expressions

Assignment 4: Context-free grammars and pushdown automata

Assignment 5: Turing machines and (un)decidability

Assignment 6: P and NP


Oral examination (20 minutes), individual.

February 21 and March 27