Theory of Algorithms
Brief introduction to the course:
Greedy and dynamic programming algorithms. Famous tricks in computer science. The most important data structures in computer science. The Chomsky hierarchy of grammars, parsing of grammars, relationship to automaton theory.Computers, Turing machines, complexity classes P and NP, NP-complete. Stochastic Turing machines, important stochastic complexity classes. Counting classes, stochastic approximation with Markov chains.
The goals of the course:
To learn dynamic programming algorithms, the most important data structures like chained lists, hashing, etc., and the theoretical background of computer science (Turing machines, complexity classes). To get an overview of standard tricks in algorithm design, and an introduction in stochastic computing.
By the end of the course, students are experts on the topic of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general.
elective live courses: regular homework, and presentation or final