Course contents *
Linear recursion with constant coefficients. The Master theorem.
Graphs. Euler circuits, Hamilton cycles. Trees. Graph coloring. Planar graphs. Euler's polyhedron formula, Kuratowski's theorem. Bipartite graphs. Hall's marriage theorem. Augmenting alternating paths. Transversals.
Integer arithmetic. Divisibility. Euclid's algorithm for the greatest common divisor. Linear Diophantine equations with two unknowns. Unique factorization. Modular arithmetic. Chinese remainder theorem. Euler's ɸ- and Möbius' μ-function. Euler's theorem and Fermat's little theorem.
Bijections, injections, surjections. Cardinality. Finite, countable and uncountable sets.
Combinatorics. Pigeon principle. Addition and multiplikation principles. Different kinds of selections. Binomial numbers, multinomial numbers. Inclusion/exclusion. Partitions and equivalence relations. Stirling numbers of the second kind.
Permutations. Cycle notation. Conjugated permutations. Even and odd permutations.
Basic group theory. Order of group elements and group. Cyclic groups. The symmetric group. Subgroups, cosets. Lagrange's theorem. Group actions on sets. Burnside's lemma.
Rings and fields. Factorization of polynomials. Irreducible polynomials. Finite fields.
Error correcting linear binary codes. RSA cryptosystem. Primality tests.