# ZZZZ

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.

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