Bonn-Aachen International Center
for Information Technology

Imprint

cosec

students

science

city life
cosec >students >Teaching >IPEC Summer 2012 
bitkey
Account 
Password 
Register?New password?

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. Berthold Vöcking

Lecture

Michael Nüsken
Konstantin Ziegler
Thomas Noll
Walter Unger

Time & Place

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

Exam

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

Credits

For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.
There will be a written exam after the end of the complete course.

Week 1 - Mathematical tools

This week will deal essentially with three subjects:

The screen notes (PDF) contain all handwritten stuff (last updated 11 October 2012, 17:28).

Addon

You might enjoy solving the geocache Felix Bauklötze.

Week 2 - Algorithms and Analysis

Agenda

  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)

Literature

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.

Imprint, webmaster & more