DM851: Applied Combinatorics (5 ECTS)

STADS: 15018601

Level
Master's level course

Teaching period
The course is offered in the autumn semester.

Teacher responsible
Email: daniel@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal.

Prerequisites:
Bachelor degree in computer science, mathematics, applied mathematics, mathematics-economy or comparable.

Academic preconditions:
Students taking the course are expected to:

• be able design and implement programs, using standard algorithmic approaches and data structures
• be able to judge the complexity of algorithms, with regard to runtime as well as with regard to space usage.

Course introduction
The aim of the course is to enable the student to understand and apply concepts necessary to generate, enumerate and analyse combinatorial structures. This is important in order to study scientific models in several disciplines as well as for the analysis and design of algorithms.

The course builds on the knowledge acquired in the courses DM551 Algorithms and Probability or MM541 Combinatorial Mathematics, DM507 Algorithms and Data Structures, and DM508 Complexity and Computability or MM539 Algebra 2.

The course gives an academic basis for writing a Master's thesis, that aims at applying and/or analyzing combinatorial approaches to problems arising in Computer Science or other disciplines including Chemistry, Mathematics, or Biology.

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

• Give knowledge on selected scientific models and methods from Computer Science, which are based on highest international research standards, including topics from state-of-the-art research
• Give knowledge of computer science models and methods for use in other professional areas
• Describe, analyse, and solve advanced computer scientific problems using the models they learned.
• Shed light on stated hypotheses with a qualified theoretical basis and be critical of both own and others research results and scientific models.
• Develop new variants of the learned methods, where the concrete problem requires it.
• Disseminate research-based knowledge and discuss professional and scientific problems with both colleagues and non-specialists.
• Plan and execute scientific projects of high standard, including managing work situations that are complex, unpredictable, and require novel solutions.
• Take responsibility of own professional development and specialisation have learned.
• Be able to launch and implement scientific and interdisciplinary cooperation and take professional responsibility

Expected learning outcome
The learning objectives of the course are that the student demonstrates the ability to:

• be able to make proper specifications of combinatorial classes
• analyse the properties of large combinatorial classes
• systematically apply generic methods from Combinatorics in order to study algorithms and scientific models that are based on combinatorial structures
• give expert knowledge about selected topics in Combinatorics, which is based on the highest level of international research
• apply modern combinatorial techniques in order to design and implement algorithms for complex combinatorial problems

Subject overview
The following main topics are contained in the course:

• Combinatorial Classes
• Generating Functions
• Combinatorial Algorithms
• Symmetry Detection
• Graph Isomorphism
• Pólya Counting
• Boltzman Sampling
• Algebraic and Combinatorial Computing with SageMath

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Programming assignments. Pass/fail, internal marking by the teacher.

Assessment and marking:
Oral exam without exam aids. Danish 7-mark scale, external marking.

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

Educational activities

Educational form
Activities during the study phase:

• Using the acquired knowledge in projects.
• Discussing the scientific articles/book chapters
• Eksperiments in SageMath

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.