Bonn-Aachen International Center
for Information Technology





crypto >Students >Teaching >Winter 2017/18 

Foundations of informatics - a bridging course

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


Dr .Michael Nüsken (contact person)
Prof. Dr. Erika Ábrahám
Prof. Dr. Ir. Gerhard Woeginger

Time & Place

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

Schedule: Mon-Fri 900 - 1230 and 1400 - 1600, each block includes 30 minutes break. (If a course week advances fast, Friday afternoon may be free.)

Some clarifications


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.

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:


You might enjoy solving the geocache Felix Bauklötze.

Week 2 - Analysis of Algorithms


  1. foundations (first examples, asymptotic notation, solving recurrence equation)
  2. sorting (QUICKSORT, sorting in linear time)
  3. data structures (linked lists, hash tables, binary search trees)
  4. graph algorithms (elementary (breadth-first, depth-first), single-source shortest path)
  5. as time permits: advanced (matrix operations, polynomial and FFT, NP-completeness)


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

  1. Regular languages
    1. Formal languages
    2. Finite automata
    3. Regular expressions
    4. Minimisation of finite automata
  2. Context-free languages
    1. Context-free grammars and languages
    2. Context-free vs. regular languages
    3. The word problem for context-free languages
    4. The emptiness problem for context-free languages
    5. Closure properties of context-free languages


Week 4 - Complexity

This course week only starts on Tuesday at 1000. Further arrangements will be made in class.

  1. Introduction to computability
  2. Undecidable problems; halting problem; theorem of Rice
  3. Recursive enumerability; PCP; Hilbert's tenth problem
  4. Introduction to complexity
  5. NP-completeness of selected graph problems
  6. NP-completeness of selected number problems

Slides and more.


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.

Impressum, webmaster & mehr

User login

Enter your username and password here in order to log in on the website


Hier einloggen
Neues Profil