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

Lectures: Thursdays 10h-12h in the lecture hall 2.73 of the physics building PER 08.
Exercises: Wednesdays 17-19h in the lecture hall 2.52 of the physics building PER 08. Exercises start on September 29.

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. For the exercise series, the weekly progress and summary videos, visit the course's Moodle page.

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 groups of three.
• 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.

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"