Skip to main content

Foundations of informatics - a bridging course

This course shall smooth the entry into the b-it/RWTH study programme Media Informatics.

About This Course

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

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
and
Week 4 - Complexity

These parts of the course are not here. Find more details about them on the course base page.

Requirements

You are supposed to have learned a variety of basic skill during your bachelor studies.

Course Staff

Frequently Asked Questions

What web browser should I use?

The Open edX platform works best with current versions of Chrome, Firefox or Safari, or with Internet Explorer version 9 and above.

See our list of supported browsers for the most up-to-date information.

Enroll