Foundations of informatics - a bridging course

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

Responsible

Lecture

Dr. Michael Nüsken (contact person)
Prof. Dr. Thomas Noll
Prof. Dr. Ir. Gerhard Woeginger

Time & Place

18 - 21 October 2016, b-it bitmax (Michael Nüsken).
24 - 28 October 2016, b-it bitmax (Michael Nüsken).
20 - 24 March 2017, b-it Rheinsaal (Thomas Noll).
10 - 13 April 2017, b-it Rheinsaal (Gerhard Woeginger).

First meeting: Tuesday(!), 18 October, 9⁰⁰. (Please ignore what may be written in BASIS or campus.)

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

During week 4, the schedule is shifted by one hour: Mon-Fri 10⁰⁰ - 12³⁰ and 14⁰⁰ - 17⁰⁰.

Exam

Exam1: Wednesday, 26 April 2017, 11⁰⁰-14⁰⁰, b-it bitmax. [Updated 24 March.]
Post-Exam1: Monday, 29 May 2017, 12³⁰-13³⁰, b-it 1.25.
Exam2 (repetition): Tuesday, 20 June 2017, 14⁰⁰-17⁰⁰, RWTH Aachen, CS Department, Lehrstuhl für Informatik 2, seminar room.
MOVED TO: Seminarraum 5054 in E2 Extension Building of the Computer Science Center. Directions, overview map.
Post-Exam2: Thursday, 20 July 2017, 14⁰⁰, b-it 1.22/1.25.

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.

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 are available on login. You obtain a login as a participant of the course or on request: In that case create a login at the key at the top left of this page via "Register" and afterwards mail the contact person mentioning this.

Addon

You might enjoy solving the geocache Felix Bauklötze.

Week 2 - Analysis of Algorithms

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.

Slides (no login)

Slides and screen notes are available on login. You obtain a login as a participant of the course or on request.

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.

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