DM528: Combinatorics, Probability, and Randomized Algorithms (5 ECTS)
STADS: 15006701Level
Bachelor course
Teaching period
The course is offered in the autumn semester.
2nd quarter
Teacher responsible
Email: lenem@imada.sdu.dkTimetable
| Group | Type | Day | Time | Classroom | Weeks | Comment |
|---|---|---|---|---|---|---|
| Common | I | Monday | 12-14 | U26 | 45-51 | |
| Common | I | Thursday | 08-10 | U26 | 45-46, 48 | |
| Common | I | Friday | 14-16 | U26 | 50 | |
| S1 | TE | Monday | 16-18 | U26 | 51 | |
| S1 | TE | Tuesday | 10-12 | U26 | 46-51 | |
| S1 | TE | Friday | 14-16 | U20 | 45 | |
| S1 | TE | Friday | 14-16 | U26 | 46-47, 49 | |
| S2 | TE | Tuesday | 10-12 | U145 | 51 | |
| S2 | TE | Wednesday | 08-10 | U35 | 45-51 | |
| S2 | TE | Thursday | 16-18 | U35 | 46-47 | |
| S2 | TE | Thursday | 14-16 | U10 | 49 |
Show personal time table for this course.
Revison of timetable:
: Hold S2 oprettet.
Comment:
Ubegrænset deltagerantal. Kurset kører i 2. kvartal.
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
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 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.
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) Mandatory assignments, pass/fail, internal evaluation by teacher. The assignments must be passed in order to take the written exam.
(b)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.
Forelæsninger: 22 timer
Eksaminatorietimer/opgaveregning: 20 timer.
Educational activities
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.
