MM541: Combinatorial Mathematics (5 ECTS)

STADS: 13012101

Level
Bachelor course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
24/02/16 er M2 nedlagt og studerende flyttet over på M1.
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
The topics from MM537 Introduction to Mathematical Methods are assumed known.

Course introduction
The course will give the students basic skills to work with combinatorical mathematics, (algorithmic) graph theory and (primarily combinatorial applications of) linear programming theory.

Qualifications
The students will gain insight into techniques for counting the number of elements in a set. They will know basic graph theory definitions as well as fundamental problems related to graphs. They will know basic theory about linear programming in particular the duality theorem. After the course the students will be able to use this knowledge in relevant situations to:

• Count the number of elements in a set
• Formulate counting problems from problems from a description in plain words
• Solve linear recursion equations
• Solve graph theoretic problems similar to those discussed in the course
• Formulate linear programs and apply the duality theorem for linear programming

Expected learning outcome
At the end of the course the student is expected to be able to:

• Apply the counting techniques from the course for finding the cardinality of a set
• Formulate counting problems based on a description in plain words
• Solve linear recurrence relations
• Solve graph theory problems which resembles those studied in the course
• Formulate linear programs for various optimization problems resembling them from the course
• Describe these actions in precise mathematical language, and argue for each of the steps of the calculations/ arguments

Subject overview
Combinatorics, counting techniques for permutations and combinations, binomial coefficients, the inclusion/exclusion principle, linear recurrence relations, graph theory (basic definitions, various routing problems, spanning trees, matchings), greedy algorithms, linear programming and duality, algorithmic proofs, good characterizations.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:

1. Oral exam partly based om written assignments. External censorship, Danish 7-mark scale (5 ECTS). (13012102)

During the course two sets of problems are posed. One of these has to be solved independently, while the other may be solved by groups of up to 3 persons. Together with selected topics from the course, these problem sets form the basis for an individual, oral exam at the end of the course.

The final grade will be based on an overall impression of the student's performance in the three elements which are part of the evaluation. The external examiner will be able to see the solutions of the two problem sets.

Reexamination in the same exam period or immediately thereafter. Oral examination, grades according to the Danish 7-point scale and external examiner.

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

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.