DM538: Algorithms and Probability (5 ECTS)

STADS: 15011601

Level
Bachelor course

Teaching period
The course is offered in the autumn semester.
1st and 2nd quarter

Teacher responsible
Email: lenem@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal. 1.+2. kvartal.

Prerequisites:
None

Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM527 or DM535 Discrete Methods for Computer Science must be known.

Course introduction
The course should give the students the skills to work with combinatorical mathematics and discrete probability, in particular in applications in computer science. In the first part of the course, the student will learn techniques for counting the number of elements in finite sets. In the second part, these techniques are used in conjunction with discrete probability spaces and distributions. Then we continue with more advanced counting techniques and in the last part, the students will learn to use the principles from the first two parts for developing and analyzing randomized algorithms. 

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.
• Apply the discrete probability techniques from the course, including analyzing central discrete probability distributions.
• Solve linear recurrence relations.
• Develop and analyze basic randomized algorithms using tools from combinatorics and discrete probability theory.
• Describe these actions in precise mathematical language, and argue for each of the steps of the calculations.

Subject overview
Combinatorics, counting techniques for permutations and combinations, binomial coefficients, the inclusion/exclusion principle, discrete probability theory, standard discrete probability distributions, recurrence relations, randomized algorithms.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
(a) Mandatory assignments, pass/fail, internal evaluation by teacher. The assignments must be passed in order to take the written exam.
(b) 3 hour written exam, 7-point grading scale, external examiner.

Reexamination after 4. quarter. 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: 26 hours, hereof:
 - Tutorials: 26 hours

Educational activities Study phase: 14 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.