DM528: Combinatorics, Probability, and Randomized Algorithms (5 ECTS)

STADS: 15004201

Level
Bachelor course

Teaching period
The course is offered in the autumn semester.
2nd. quater

Teacher responsible
Email: jbj@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal

Prerequisites:
None

Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM527 Mathematical Tools 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
- Apply the counting techniques from the course for finding the cardinality of a set.
- Apply the discrete probability techniques from the course, including finding expectation and variance for central discrete probability distributions.
- Solve linear recurrence relations and perform asymptotic analysis of the growth of functions given by non-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, generating functions, randomized algorithms.

Literature

Meddeles ved kursets start

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
(a) Madatory assigments, pass/fail, internal evaluation by teacher.
(b)Written exam, Danish 7-mark scale, external examiner.

Reexamination after 4. quarter. Oral examination, grades according to the danish 7-point scale and external censorship.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 22 timer
Eksaminatorietimer/opgaveregning: 20 timer.
Educational activities

Language
This course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.