to Ivan Izmestiev's homepage

Mathematical Methods for Computer Science / Discrete Mathematics, University of Fribourg 2017/18

Date Topics Homework
20 Sep Basic counting techniques. Series 1.
27 Sep Binomial coefficients. Series 2.
4 Oct Multinomial coefficients. Inclusion-exclusion formula. Series 3.
11 Oct Graphs. Eulerian and Hamiltonian graphs. Series 4.
18 Oct Trees. Kruskal's algorithm for a minimum spanning tree. Series 5.
25 Oct Planar graphs. Series 6.
02 Nov Matchings. Series 7.
8 Nov Truth tables, tautologies, DNF and CNF. Series 8.
22 Nov Hilbert's proof systems. Series 9.
29 Nov Gentzen's proof systems. Series 10.
6 Dec Predicate logic: syntax and semantics. Series 11.
13 Dec Proof theory in predicate logic. Series 12.
20 Dec Skolem form and Herbrand universe. Bonus series.
21 Feb Fibonacci and other recursive sequences. Series 1.
28 Feb Generating functions. Series 2.
8 Mar Partitions. Series 3.
14 Mar Partitions, continued. Series 4.
21 Mar Catalan numbers. Series 5.
28 Mar Deterministic and nondeterministic finite automata. Series 6.
11 Apr Automata with ε-transitions; regular expressions. Series 7.
18 Apr Regular expressions and regular languages. Series 8.
25 Apr The pumping lemma and homomorphisms. Series 9.
02 May The Myhill-Nerode theorem. Series 10.
09 May Context-free grammars. Series 11.
16 May Pushdown automata. Series 12.
23 May Properties of context-free languages. Series 13.

Literature

Exam information

Two (for mathematicians three) handwritten A4 sheets are the only allowed sources.