Foundations of Computer Science (FM 2), Winter Term 2024/25
| Lecturer: | PD Dr. Henning Bordihn |
| Program: | Master of Cognitive Systems and Master of Data Science |
| SWS: | 4 (2 h/week classroom presence) |
| Credits: | 6 |
| Module: | FM 2 (Bridging Module) |
Schedule
| Form: Consultation | Time: Thursday, | 16:15-17:45, | 02.70.0.08 | First Meeting: 16.10.25 |
Content
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
- Algorithms and their complexity; Growth of functions
- Algorithmic Paradigms (Recursion, Divide and Conquer, Dynamic Programming)
- Fast algorithms (searching, sorting, ...)
2. Theory of Computation
- Finite state automata
- Determinism versus non-determinism
- Regular expressions
- Context-free grammars and pushdown automata
- Turing machines and undecidability
- NP-completeness
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
As I am unfortunately unavailable on both December 5 and December 11, we have to postpone our meetings. We will discuss the topic from assignment 3 on December 18th.
Rescheduled: Meeting on December 18 and NO meeting on December 4 and 11!
Assignment 4: Context-free grammars
Rescheduled: We will discuss the topic from assignment 4 on January 8.
Assignment 5: Pushdown automata and context-free languages
Rescheduled: We will discuss the topic from assignment 5 on January 15.Examination
Oral examination (25 minutes), individual.