Foundations of informatics - a bridging course

Corresponding entry in Bonn Basis.

Responsible

Prof. Dr. Joachim von zur Gathen
Prof. Dr. Berthold Vöcking

Lecture

Michael Nüsken
Konstantin Ziegler
Thomas Noll
Walter Unger

Time & Place

11 - 14 October 2011, b-it bitmax (Michael Nüsken).
17 - 21 October 2011, b-it bitmax (Konstantin Ziegler).
05 - 09 March 2012, b-it Marschallsaal (Thomas Noll).
12 - 16 March 2012, b-it Marschallsaal (Walter Unger).

Schedule: Mon-Fri 9⁰⁰ - 12³⁰ and 14⁰⁰ - 16⁰⁰, each block includes 30 minutes break. (If a course week advances fast, Friday afternoon may be free.)

Exam

Exam1: Friday, 16 March 2012, 14⁰⁰, b-it Marschallsaal.
Post-Exam1: Wednesday, 18 April 2012, 15³⁰, b-it 1.25.
Exam2 (repetition): Monday, 21 May 2012, 14⁰⁰, Aachen "Seminar Room of Lehrstuhl für Informatik 2" (room 4201b, 2nd floor, building E 1).
Post-Exam2: Wednesday, 20 June 2012, 15³⁰, b-it 1.25.

The exam is about the entire course. Please note that the second exam is for repetitions.

Credits

For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.
There will be a written exam after the end of the complete course.

Week 1 - Mathematical tools

This week will deal essentially with three subjects:

Linear Algebra (Gaussian elimination, 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, ...).

The screen notes (PDF) contain all handwritten stuff (last updated 17 October 2011, 18:07).

Addon

You might enjoy solving the geocache Felix Bauklötze.

Week 2 - Algorithms and Analysis

Agenda

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)

Literature

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.

Week 3 - Regular Languages, Context-Free Languages, Processes and Concurrency

Week 4 - Complexity

Allocation

equivalent V4+Ü4
Note that all Media informatics courses only start in the third week of the lecturing period, so that everybody can participate in this course.