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

- Matousek, Nesetril "Invitation to discrete mathematics"
- Aigner "A course in enumeration"
- Bondy, Murty "Graph theory with applications"
- Gallier "Logic for computer science"
- Huth, Ryan "Logic in computer science"
- Hopcroft, Ullman "Introduction to automata theory, languages, and computation"

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.