Discrete Mathematics

2019-2020
Dit vak wordt in het Engels aangeboden. Omschrijvingen kunnen daardoor mogelijk alleen in het Engels worden weergegeven.

Doel vak

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

Inhoud vak

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

Onderwijsvorm

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.

Toetsvorm

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.

Vereiste voorkennis

Basic Concepts in Mathematics

Literatuur

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)

Doelgroep

First year BSc Mathematics

Overige informatie

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.

Algemene informatie

Vakcode XB_0008
Studiepunten 6 EC
Periode P2
Vakniveau 100
Onderwijstaal Engels
Faculteit Faculteit der Bètawetenschappen
Vakcoördinator dr. S.R. Dahmen
Examinator dr. W. Kager
Docenten dr. S.R. Dahmen

Praktische informatie

Voor dit vak moet je zelf intekenen.

Voor dit vak kun je last-minute intekenen.

Werkvormen Werkcollege, Deeltoets extra zaalcapaciteit, Hoorcollege
Doelgroepen

Dit vak is ook toegankelijk als: