Foundations of informatics - a bridging course

This course is not listed in Aachen Campus and listed in Bonn Basis as Foundations of Informatics.

Responsible

Prof. Dr. Joachim von zur Gathen
Prof. Dr. Thomas Noll

Lecture

Michael Nüsken (contact person)
Daniel Loebenberger
Walter Unger
Thomas Noll

Time & Place

7 - 10 October 2014, b-it bitmax (Michael Nüsken).
13 - 17 October 2014, b-it bitmax (Daniel Loebenberger).
2 - 6 March 2015, b-it Rheinsaal (Walter Unger).
16 - 20 March 2015, b-it Rheinsaal (Thomas Noll).

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: 20 March 2015, 13⁰⁰-16⁰⁰, b-it Rheinsaal.
Post-Exam1: 16 April 2015, 14⁰⁰, b-it 1.25.
Exam2 (repetition): 18 May 2015, 16⁰⁰-19⁰⁰, RWTH Aachen Room 4017 (institute I1 seminar room, extension building E1).
Post-Exam2: 2 July 2015, 13⁰⁰, b.it 1.25.

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

Week 1 - Mathematical tools

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, ...).

The screen notes (PDF) contain all handwritten stuff (last updated 10 October 2014, 16:44).

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 - Complexity

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

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.

For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.