DM891: Algorithms under Stochastic Uncertainty
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340124102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master
STADS ID (UVA): N340124101
ECTS value: 5
Date of Approval: 07-10-2022
Duration: 1 semester
Version: Approved - active
Comment
The course is offered as required and is not necessarily offered every year. Exam attempts for DM891 are offered in accordance to the following plan, when the course is offered. Spring (course Start February): ordinary Exam (June), first re-examination (August) and second re-examination (January).
Entry requirements
Academic preconditions
Knowledge of algorithms and data structures and their analysis is assumed, including algorithm-design techniques such as greedy approaches and dynamic programming, basic graph algorithms, time and space analysis, including asymptotic notation, and basic understanding of probability theory. The prerequisites can be obtained through algorithms and discrete mathematics courses on a computer science bachelor education.
Course introduction
The purpose of this course is to introduce algorithmic problems that involve stochastic uncertainty and study algorithmic techniques for them as well as their computational complexity. The real-world problems that can be modelled with the considered problems include hiring processes, selling goods to customers, decision making under information cost, and classifying the risk of a patient. The availability of stochastic information can be motivated with the availability of big data.
The course builds on the knowledge acquired in the courses DM549 Discrete Methods for Computer Science or MM537 Introduction to Mathematical Methods, DM551 Algorithms and Probability or MM541 Combinatorial Mathematics, DM507 Algorithms and Data Structures, and DM553 Complexity and Computability. The course gives the basis for writing a Master’s thesis on algorithms under stochastic uncertainty.
In relation to the competence profile of the degree, it is the explicit focus of the course to:
- give the competence to comprehend complex problems,
- give expert knowledge based on recent high-level international research,
- give the competence to work on complex assignments towards a solution,
- give the competence to communicate scientific problems and solutions through written assignments.
Expected learning outcome
The learning objective of the course is that the student demonstrates the ability to:
- define and compare the problems studied in the course.
- identify real-world problems that can be modelled with the abstract problems studied in the course.
- describe and execute the algorithms studied in the course.
- conduct the algorithm analyses studied in the course.
- prove upper and lower bounds for performance guarantees of algorithms for problems related to those studied in the course.
- design and analyze new algorithms for problems resembling those studied in the course.
Content
The following main problems are considered in the course:
- the secretary problem, variants, and extensions,
- the prophet-inequality problem, variants, and extensions,
- problems involving Markov chains and Markov decision processes,
- the Pandora’s box problem and extensions,
- stochastic probing problems,
- problems of evaluating stochastic functions.
If the respective aspect is feasible for the problem at hand, exact algorithms, algorithms with provable performance guarantees, computational complexity, and adaptivity gaps will be discussed.
Literature
Examination regulations
Exam element a)
Timing
June
Tests
Oral examination
EKA
N340124102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Duration
30 minutes
Examination aids
To be announced during the course
ECTS value
5
Additional information
In addition to the oral exam, a number of individual assignments handed in during the course. The grade is based on an overall impression of the elements included in the evaluation.
Indicative number of lessons
Teaching Method
At the Faculty of Science, teaching is organized after the three-phase model, i.e., intro, training, and study phase.
- Intro phase: 22 hours.
- Training phase: 14 hours.
Activities during the study phase:
- solution of weekly assignments in order to discuss these in the exercise sections,
- solving the mandatory assignments,
- self study of various parts of the course material,
- reflection upon the intro and training sections.
Teacher responsible
Timetable
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Transition rules
Transitional arrangements describe how a course replaces another course when changes are made to the course of study.
If a transitional arrangement has been made for a course, it will be stated in the list.
See transitional arrangements for all courses at the Faculty of Science.