Discrete Mathematics

COURSE OBJECTIVE
- The student knows basic concepts from graph theory and can solve problems about and with those in explicit situations.
- The student knows basic theorems and algorithms from graph theory and can use these to compute and/or prove certain properties in explicit situations.
- The student knows basic concepts from combinatorics and can solve problems about and with those in explicit situations.
- The student knows basic theorems and techniques from combinatorics and can use these to compute and/or prove certain properties in explicit situations.

COURSE CONTENT
This course is about two (related) subjects, namely Graph Theory and Combinatorics.

A graph consists of points (or vertices) and lines (or edges) connecting pairs of points. Graphs occur as mathematical models for many situations in both pure and applied mathematics. Combinatorics involves formulas and techniques for enumeration.

We treat the following topics.
- Elementary graph concepts
- Trees, spanning trees
- Eulerian and Hamiltonian trails/circuits
- Planarity
- Matchings, flows
- Binomial coefficients and generalisations
- Pigeonhole and inclusion-exclusion principles
- Generating functions
- Recurrence relations
- Permutation groups

TEACHING METHODS
Lectures, study sessions and tutorials (total 8 hours per week). Students are also required to hand in a homework assignment every week.
We expect you to dedicate in total about 20 hours per week to this course.

TYPE OF ASSESSMENT
Your final grade is built up as follows:

- a written midterm exam (50%);
- a written final exam (50%).

You will also be required to hand in 6 written assignments. Each of which will be graded as “sufficient” or “insufficient”. A hand-in
assignment that is initially graded as “insufficient”, may be handed in a second time.

ENTRY REQUIREMENTS
Basic Concepts in Mathematics