English

MM541: Combinatorial Mathematics (5 ECTS)

STADS: 13012101

Level
Bachelor course

Teaching period
The course is offered in the spring semester.

Teacher responsible

Email: yeo@imada.sdu.dk

Timetable

Group	Type	Day	Time	Classroom	Weeks
Common	I	Monday	12-14	U56	6-12
Common	I	Wednesday	14-16	U56	5
Common	I	Thursday	14-16	U24	5-6
Common	I	Thursday	14-16	U43	8-9,11
H16	TE	Tuesday	10-12	U56	6-12
H16	TE	Thursday	14-16	U24	7
H16	TE	Thursday	14-16	T9	10
H16	TE	Thursday	14-16	U154	12
H16	TE	Friday	08-10	U10	5
H17	TE	Wednesday	14-16	U56	6-9,11-12
H17	TE	Thursday	08-10	U30A	10
H17	TE	Friday	13-15	U24	5
H17	TE	Friday	13-15	U142	7
H17	TE	Friday	13-15	U14	10
H17	TE	Friday	13-15	T9	12

Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
Students taking the course are expected to have knowledge of the topics from MM537 (Introduction to Mathematical Methods).

Course introduction

The course will teach the student to use methods from combinatorial mathematics, (algorithmic) graph theory and (primary combinatorial use of) linear programming.

These skills are important when new algorithms are being developed and when practical problems need to be optimised. It is furthermore important for the understanding of why the given algorithms and methods work.

The course builds on the knowledge of logic and formulating proofs acquired in the course MM537. It is thus presupposed that the student can formulate simple proofs.

If the course is supplemented with other courses in similar areas it is possible to write a BA-project in discrete mathematics.

In relation to the competence profile of the degree it is the explicit focus of the course to:

Give knowledge and understanding of selected mathematical subjects such as linear programming and counting techniques.
Give knowledge and understanding of using discrete models and be able to criticize such models.
Give skills and competence in the use of the above.

Expected learning outcome

The learning objective of the course is that the student demonstrates the ability to:

Count the number of elements in a set.
Formulate counting problem based on a written description.
Solve linear recursion equations.
Solve graph theoretical problems similar to the ones given in the course.
Formulate linear programming problems and use the duality theorem.

Subject overview

The following main topics are contained in the course:

Combinatorics
Techniques for counting permutations and combinations.
Binomial coefficients.
Inclusion/exclusion.
Linear recursion equations.
Graph Theory (definitions, transportation problems, spanning trees and matchings).
Greedy algorithms.
Linear programming and duality.
Algorithmic proofs.
Good characterizations.

Literature
There isn't any litterature for the course at the moment.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:

Expected working hours
The teaching method is based on three phase model.
Intro phase: 26 hours
Skills training phase: 22 hours, hereof:
- Tutorials: 22 hours

Educational activities Study phase: 30 hours

Self study of the teaching material.
Solving weekly assignments in order to discuss these at the tutorials.
Written assignments as part of the exam.
Self guided follow up on the intro and tutorial classes
Repetition for the exam

Educational form
The course consists of lectures and problem sessions. During the course there is also two problem sets, where one is solved individually and the other in a group of up to 3 people.

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.