# 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 bitmax (0.109), (Endenicher Allee 19A). - Post-Exam1:
Tuesday, 7 May 2019, 13
^{00}-14^{00}, b-it 2.121. - Exam2 (repetition):
Friday, 7 June 2019, 10
^{00}-13^{00}, RWTH Aachen, seminar room 9U10 in building E3 of the computer science center. - Post-Exam2: Thursday, 1 August 2019, 11
^{00}, b-it 2.122 (or later by personal appointment).

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

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

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

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