#
Foundations of informatics - a bridging course
Enrollment is Closed

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.