# Foundations of informatics - a bridging course

This course is listed in Aachen online as Foundations of informatics - a bridging course and listed in Bonn Basis as Foundations of Informatics - a bridging course.

## Lecture

Dr .Michael Nüsken (contact person)

Prof. Dr. Thomas Noll

Prof. Dr. Ir. Gerhard Woeginger

## Time & Place

- 9 - 12 October 2018, b-it 0.109 (Michael Nüsken).
- 15 - 19 October 2018, b-it 0.109 (Michael Nüsken).
- 18 - 22 March 2019, b-it 0.109 (Thomas Noll).
- 25 - 29 March 2019, b-it 0.109 (Gerhard Woeginger).

First meeting: Tuesday(!), 9 October, 9^{00}.

Schedule: Week 1/2: Mon-Fri 9^{00} - 12^{30} and 14^{00} - 16^{00}, each block includes 30 minutes break. (If a course week advances fast, Friday afternoon may be free.)

Week 3/4: Mon-Fri 10^{00} - 12^{30} and 14^{00} - 17^{00}, each block includes 30 minutes break.

## Some clarifications

- The course takes place at the b-it on Campus Poppelsdorf, Bonn.
- 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, you have to arrange with the collision.
- 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.

## Exam

#### Exam hints

Verify whether your exam exercise sheets are complete: It should contain Exercise 1 to Exercise ??. Insert your name and matrikel (student number) **on each sheet**. Approaches, solutions and all side calculations must be written to the given paper. Please use also the back sides. If you need extra paper ask the supervisor. **Do not remove the staple!**

**Do write with blue or black ink!**

Do *not* use a pencil or any other erasable pen.

The exam must be handled independently. Permitted auxiliary means are: writing materials, a pocket calculator (non-programmable, without division with remainder, without linear algebra software), and a crib sheet, DIN A4, two-sided, written only with your own handwriting. Any other utilities, even own paper, are not permitted.

** An attempt at deception leads to failure for this exam and possibly other measures - even if the attempt is only detected later. **

The exam will carry the hints displayed on the right.

- Exam1:
Friday, 5 April 2019, 10
^{00}-13^{00}, b-it tba, (Endenicher Allee 19A). - Post-Exam1: tba, b-it tba.
- Exam2 (repetition):
Friday, 7 June 2018, 10
^{00}-13^{00}, RWTH Aachen, seminar room 9U10 in building E3 of the computer science center. - Post-Exam2: tba, b-it tba.

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

As a participant you obtain a password in the course or on request to access the screen notes via sciebo.

#### 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, binary search trees)
- graph algorithms (elementary (breadth-first, depth-first), single-source shortest path)

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

As a participant you obtain a password in the course or on request to access the screen notes via sciebo.

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

### Regular Languages

- Formal Languages
- Finite Automata
- Regular Expressions
- Minimization of Deterministic Finite Automata
- The Pumping Lemma

### Context-Free Languages

- Context-Free Grammars and Languages
- Context-Free and Regular Languages
- Decidability Problems of Context-Free Languages
- Closure Properties of Context-Free Languages
- Pushdown Automata

## Week 4 - Complexity

- 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

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