to Ivan Izmestiev's homepage

Mathematical Methods for Computer Science / Discrete Mathematics, University of Fribourg 2018/19

Lecture notes. (Updated weekly.)

Date Topics Homework
19 Sep Basic counting techniques. Series 1.
26 Sep Binomial coefficients. Series 2.
3 Oct Multinomial coefficients. Inclusion-exclusion formula. Series 3.
10 Oct Graphs. Handshake lemma. Eulerian graphs. Series 4.
17 Oct Trees. Spanning trees. Kruskal's algorithm. Series 5.
24 Oct Planar graphs. Series 6.
31 Oct Matchings. Series 7.
7 Nov Propositional logic: syntax and semantics. Series 8.
21 Nov DNF and CNF. Hilbert's proof system. Series 9.
28 Nov Sequent calculus in propositional logic. Series 10.
5 Dec Predicate logic: syntax and semantics. Series 11.
12 Dec Sequent calculus in predicate logic. Series 12.
19 Dec G\"odel's incompleteness theorem.
20 Feb Linear recursive sequences. Series 1.
27 Feb Generating functions. Series 2.
6 Mar Partitions: generating function. Series 3.
13 Mar Partitions: Ferrers diagrams and recursive relations. Series 4.
20 Mar Catalan numbers. Series 5.
27 Mar DFAs and NFAs. Series 6.
3 Apr ε-NFAs. Regular expressions. Series 7.
10 Apr Regular languages and regular expressions. Series 8.
17 Apr Pumping lemma and homomorphisms. Series 9.
01 May Myhill-Nerode theorem and minimization of DFAs. Series 10.
08 May Context-free grammars. Chomsky form. Series 11.
15 May Pushdown automata. Equivalence with context-free grammars. Series 12.
22 May Pumping lemma for context-free languages. Closure and non-closure properties. Series 13.

Literature

Homework

Students who take this course as "Mathematical methods for CS" have to achieve 60% of points in the homework assignments.

Exam information

MMCS: a written exam (2 hours) at the end of every semester.
DiscrMath: a written exam (2 hours) at the end of the academic year.
Two (for mathematicians four) handwritten A4 sheets can be taken to the exam.
Exam requirements: you should be familiar with concepts and theorems introduced in the lecture. You can use theorems from the course without giving their proofs, but please describe exactly what theorem you are using.