Foundations of Computer Science
The course covers the following foundational topics:
- algorithms and data structures: growth of functions and O-notation, divide-and-conquer, sorting and searching, elementary data structures, dynamic programming, greedy algorithms, elementary graph algorithms
- formal language theory: Chomsky hierarchy, regular languages and finite-state automata, context-free languages and push-down automata, finite-state transducers, Turing machines
- other theoretical foundations: computability, halting problem, nondeterminism, recursion, lists and trees).
Prof. Dr. Tobias Scheffer