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

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

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

To pass the course in period 2 you must satisfy the following
requirements:

- your final grade must be at least 5.5 (all students); and
- at least 5 out of your 6 hand-in assignments must have been graded as
"sufficient" (all students); and
- you must have been present in at least 75% of the study sessions and
tutorials (full time students only).

If you do not fulfill these requirements, then you can take the resit
exam. The resit exam then counts for 100% (i.e. any grades from the
midterm and/or final exam in period 2 will no longer be valid) and the
only requirement to pass is to score at least 5.5 on this exam.

Entry Requirements

Basic Concepts in Mathematics

Literature

John M. Harris, Jeffry L. Hirst and Michael J. Mossinghoff,
Combinatorics and Graph Theory (second edition), Springer-Verlag, 2008,
ISBN: 978-0-387-797710-6 (available form the library as e-book)

Additional Information Target Audience

First year BSc Mathematics

Additional Information

Participation in at least 75% of the study sessions and tutorials is
mandatory (for full time students) in order to pass the course in period
2. This rule does not apply to the resit exam.