DM538: Algorithms and Probability (5 ECTS)
STADS: 15012501
Level
Bachelor course
Teaching period
The course is offered in the autumn semester.
Teacher responsible
Email: jbj@imada.sdu.dk
Timetable
Group |
Type |
Day |
Time |
Classroom |
Weeks |
Comment |
Common |
I |
Tuesday |
12-14 |
U91 |
36-41,44-46 |
|
Common |
I |
Tuesday |
12-14 |
IMADA |
47-49 |
|
Common |
I |
Wednesday |
12-14 |
U133 |
40 |
|
Common |
I |
Friday |
12-14 |
U26a |
36-37 |
|
H1 |
TE |
Thursday |
10-12 |
U49 |
36 |
|
H1 |
TE |
Thursday |
10-12 |
U24a |
37-39 |
|
H1 |
TE |
Thursday |
10-12 |
U23a |
40 |
|
H1 |
TE |
Thursday |
10-12 |
U143 |
41 |
|
H1 |
TE |
Thursday |
10-12 |
U145 |
44-47 |
|
H1 |
TE |
Thursday |
10-12 |
U142 |
48-49 |
|
H1 |
TE |
Thursday |
10-12 |
U154 |
50-51 |
|
Show entire timetable
Show personal time table for this course.
Comment:
Ubegrænset deltagerantal. Undervises fælles med DM551 Algoritmer og sandsynlighed (10 ECTS)
Prerequisites:
None
Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM527 or DM535 Discrete Methods for Computer Science must be known. The course cannot be followed if you have passed DM551, or if you have DM551 mandatory in your curriculum.
Course introductionThe 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 outcomeAt 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 overviewCombinatorics, counting techniques for permutations and combinations, binomial coefficients, the inclusion/exclusion principle, discrete probability theory, standard discrete probability distributions, recurrence relations, randomized algorithms.
LiteratureMeddeles ved kursets start.
Website
This course uses
e-learn (blackboard).
Prerequisites for participating in the exam
Prerequisite test consisting of mandatory assignments. The assignments must be passed in order to take the written exam. (15012512)
Assessment and marking:
4 hour written exam, 7-point grading scale, external examiner. (15012502)
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: 26 hours, hereof:
- Tutorials: 26 hours
Educational activities
Study phase: 10 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.