- 10 - 13 October 2017, b-it bitmax (Michael Nüsken).
- 16 - 20 October 2017, b-it bitmax (Michael Nüsken).
- 12 - 16 March 2018, NEW BUILDING: b-it 0.107 (Erika Ábrahám).
- 3 - 6 April 2018, NEW BUILDING: b-it 0.107 (Gerhard Woeginger).
First meeting: Tuesday(!), 10 October, 900.
(Please ignore what may be written in BASIS or campus.)
Schedule: Mon-Fri 900 - 1230 and 1400 - 1600, each block includes 30 minutes break. (If a course week advances fast, Friday afternoon may be free.)
- The course takes place at the b-it in Bonn, NEW BUILDING.
- There is no access to any video or audio transmission or recording.
- The courses of the Media Informatics program only start after the first two weeks of the bridging course.
- A similar agreement for the Software Systems Engineering program does not exist.
- For some students this course is compulsary. That means: you have to pass the exam eventually. To write it you have two occasions every year, typically in April and June.
The exam will carry the hints displayed on the right.
- Exam1: Friday, 13 April 2018, 1000-1300, b-it bitmax (0.109, Endenicher Allee 19A).
- Post-Exam1: Monday, 4 June 2018, 1000-1100, b-it 2.122 and Monday, 11 June 2018, 1100-1130, b-it 2.121.
- Exam2 (repetition): Friday, 15 June 2018, 1000-1300, RWTH Aachen, Ahornstrasse 55, Building E1, Raum 4017 (Seminarraum des i1). ATTENTION! Room was changed!
- Post-Exam2: Wednesday, 5 September 2018, 1300-1400, b-it 2.121.
The exam is about the entire course. Please note that the second exam is for repetitions.
You do not need to register for either exam. An email would be nice, if you are not on the lists composed in autumn.
The exam is offered twice a year. There is no further limit on the number of attempts.
This week will deal essentially with three subjects:
- Linear Algebra (Gauß-Jordan-algorithm, expansion, dim ker A + dim im A = n, ...),
- Probabilities (Definitions, conditional probabilities, random variables, expected runtime of a random exit loop, some applications, ...),
- Integers modulo N (Definition, inversion and extended Euclidean algorithm, square and multiply, exponentiation, Theorem of Lagrange, of Euler and Fermat's little theorem, RSA correctness and efficiency, ...).
You might enjoy solving the geocache Felix Bauklötze.
- foundations (first examples, asymptotic notation, solving recurrence equation)
- sorting (QUICKSORT, sorting in linear time)
- data structures (linked lists, hash tables, binary search trees)
- graph algorithms (elementary (breadth-first, depth-first), single-source shortest path)
- as time permits: advanced (matrix operations, polynomial and FFT, NP-completeness)
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
- Goldreich, Computational Complexity: A conceptual perspective, Cambridge University Press, 2008.
- Knuth, TAOCP, Vol. 1 -- Fundamental Algorithms, 3rd edition, Addison-Wesley.
- Regular languages
- Formal languages
- Finite automata
- Regular expressions
- Minimisation of finite automata
- Context-free languages
- Context-free grammars and languages
- Context-free vs. regular languages
- The word problem for context-free languages
- The emptiness problem for context-free languages
- Closure properties of context-free languages
- J. E. Hopcroft, R. Motwani, J. D. Ullmann:
Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001.
- A. Asteroth and C.~Baier:
Theoretische Informatik, Pearson Studium, 2002.
(software for experimenting with formal languages and automata)
This course week only starts on Tuesday at 1000. Further arrangements will be made in class.
- Introduction to computability
- Undecidable problems; halting problem; theorem of Rice
- Recursive enumerability; PCP; Hilbert's tenth problem
- Introduction to complexity
- NP-completeness of selected graph problems
- NP-completeness of selected number problems
Note that all Media informatics courses only start in the third week of the lecturing period, so that everybody can participate in this course.
For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.