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