Mathematical Methods for Computer Science / Discrete Mathematics

Mathematical Methods for Computer Science / Discrete Mathematics
2020-2021 in Fribourg

Lectures: Thursdays 10h-12h in the lecture hall 2.73 of the physics building PER 08. Starting from 2.11: On Microsoft Teams until further notice (see Moodle for access).
Exercises: Wednesdays 17-19h in the lecture hall 2.52 of the physics building PER 08. Starting from 2.11: On Microsoft Teams until further notice (see Moodle for access).

Content

Fall semester: Basic combinatorics such as counting rules, binomial and multinomial coefficients and the inclusion-exclusion principle. Graph theory, Propositional and predicate logic.
Spring semester: Advanced combinatorial topics such as generating functions and Catalan numbers. Formal languages and finite automata.

Program
The course will follow these Lecture notes. The program below is updated weekly and shows our progress. See also the course's Moodle page.

Fall 2020	Exercises
17 September: Basic counting techniques. Chapter 1, Sections 1-2, up to the statement of Theorem 2.11 (unordered choices).	Series 1
24 September: Binomial coefficients. Chapter 1, from the statement of Theorem 2.11 (unordered choices) up to the end of Section 3.	Series 2
1 October: Multinomial coefficients, inclusion-exclusion formula. Chapter 1, Sections 4-5.	Series 3
8 October: Basics of graph theory. Chapter 2, Section 1 up to the statement of Theorem 1.18.	Series 4
15 October: Trees. Chapter 2, rest of Section 1 and Section 2 up to the proof that the output of Kruskal's algorithm is a tree.	Series 5
22 October: Planar graphs. Chapter 2, rest of Section 2 and Section 3 up to Duality for embedded graphs (Section 3.4).	Series 6
29 October: Matchings. Chapter 2, Section 4.	Series 7
5 November: Intro to propositional logic. Chapter 3, Sections 1.1-1.3.	Series 8
12 November: Boolean functions, proof theories. Chapter 3, Sections 1.4-2.2.	Series 9
19 November: Sequent calculus for propositional logic. Chapter 3, Sections 2.3-2.8.	Series 10
26 November: Intro to predicate logic. Chapter 4, Sections 1.1-1.4.	Series 11
3 December: Sequent calculus for predicate logic. Chapter 4, Sections 1.5-2.3.	Series 12
10 December: Gödel's incompleteness theorem. Chapter 4, Section 3.
17 December: Question session.
Spring 2021	Exercises
25 February: Linear recursive sequences. Chapter 5, Section 1.	Series 1
4 March: Generating functions. Chapter 5, Sections 2.1-2.3.	Series 2
11 March: Generalised binomial theorem, partitions of integers. Chapter 5, Sections 2.4-3.5.	Series 3
18 March: Partitions of integers. Chapter 5, Sections 3.6-3.9.	Series 4
25 March: Catalan numbers. Chapter 5, Section 4.	Series 5
1 April: Finite automata. Chapter 6, Sections 1.1-1.3.	Series 6
15 April: Automata with epsilon-transitions, regular expressions. Chapter 6, Sections 1.4-2.2.	Series 7
22 April: Regular languages and the pumping lemma. Chapter 6, Sections 2.2-3.2.	Series 8
29 April: Homomorphisms and the Myhill-Nerode theorem. Chapter 6, Sections 3.3-4.2.	Series 9
6 May: Context-free grammars and languages. Chapter 6, Sections 4.3-5.2.	Series 10
13 May: no lecture (Ascension).	Series 11
20 May: Context-free languages and pushdown automata. Chapter 6, Sections 6 and 7.	Series 12
27 May: Turing machines, question session. Chapter 6, Section 8.
3 June: no lecture (Corpus Christi).

Exercises

There will be a total of 12 exercise sheets per semester. In order to be allowed to the exam of the respective semester, students who take this course as Mathematical Methods for Computer Science have to get their solution to 9 exercise sheets accepted. A solution gets accepted if it shows that you worked thoroughly on at least three problems on the sheet. You can work in pairs.
Completed homework assignments are to be handed in before Monday noon, either via Moodle or in the appropriate box next to the room 2.52. Until further notice: only handing in via Moodle.

Exam information

MMCS: a written exam (2 hours) at the end of every semester, open book exam.
Discrete Math: a written exam (2 hours) at the end of the academic year. Four handwritten A4 sheets can be taken to the exam (you can write on both sides of the sheet).
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. You will be expected to be able to solve new exercise-style problems.

Literature

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"