DM551: Algorithms and Probability
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N330012112, N330012102
Assessment: Second examiner: None, Second examiner: External
Grading: Pass/Fail, 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Bachelor
STADS ID (UVA): N330012101
ECTS value: 10
Date of Approval: 14-03-2022
Duration: 1 semester
Version: Approved - active
Comment
DISCONTINUED - offered last time Autumn 2023
Exam attempts are held January 2024
Exam attempts are held March 2024
Exam attempts will be held in August 2024
The course has joined classes with MM851.
Entry requirements
Academic preconditions
Students taking the course are expected to:
- Have knowledge of basic datastructures
- Have knowledge of basic algorithms for manipulating (representations of) sets of numbers and graphs as well as implementations of such in an imperative programming language.
- Be able to use basic mathematical argumentation, including proof by induction, proof by contradiction and logic expressions
- Know about convergence of power series
Course introduction
The aim of the course is to enable the student to use methods from combinatorics and discrete probability in connection with the design and analysis of algorithms and data structures. This is important both in the process of developing new algorithms for a given problem and when one wants to estimate, which among several algorithms and implementations of these via data structures, can be expected to have the best performance.
The course builds on the knowledge acquired in the courses DM507 Algorithms and data structures and DM549 Discrete methods for Computer science.
The course forms the basis for doing a bachelor project as well as elective candidate level courses containing one or more of the following elements: flows in networks, randomisation, counting arguments for complexity or correctness of algorithms as well as probabilistic proofs. Together with courses as above this course also provides a basis for doing a master’s thesis on randomised algorithms.
In relation to the competence profile of the degree it is the explicit focus of the course to:
- Give the competence to develop and analyse algorithms based on methods from combinatorics and discrete probability
- Give the competence to apply combinatorial arguments as well as discrete probability in connection with development and analysis of algorithms and data structures
- Give knowledge and understanding of the probabilistic method
- Give an understanding of how to apply methods from combinatorics and randomisation in the design and analysis of algorithms with good expected running time/performanc
- Give knowledge of randomised design of algorithms and the use of elementary probability theory to analyse the running time of algorithms
- Give competencies in developing new variants of key algorithms and data structures in the field of computer science
Expected learning outcome
The learning objectives of the course are that the student demonstrates the ability to:
- Apply the counting techniques from the course to determine the cardinality of a set
- Apply the topics on discrete probability from the course to, among other things, central probability distributions as well as to estimate the expected running time of algorithms
- Solve linear recurrence relations
- Develop and analyse basic randomized algorithms based on topics from the course
- Apply techniques from universal hashing to choose hash functions with good expected performance
- Apply algorithms from the course to find occurrences of a given text string in a text
- Construct a finite automaton corresponding to the string matching problem for a given text pattern.
- Formulat a flowmodel for problems that resemble those covered in the course
Content
The following main topics are contained in the course:
- Combinatorics
- Counting techniques including, permutations, combinations, binomial coefficients, distributing objects in boxes and the inclusion-exclusion principle
- Linear recurrence equations
- Discrete probability and discrete probability distributions
- Randomized algorithms
- Probabilistic analysis of algorithms
- The probabilistic method
- Universal hashing
- String matching
- Flows in networks
Literature
Examination regulations
Prerequisites for participating in the exam a)
Timing
Autumn
Tests
Mandatory assignments
EKA
N330012112
Assessment
Second examiner: None
Grading
Pass/Fail
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
0
Additional information
The prerequisite examination is a prerequisite for participation in exam element a).
Exam element a)
Timing
January
Tests
Oral examination
EKA
N330012102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
10
Additional information
Oral exam as well as a number of assignments handed in during the course. The grade is based on an overall impression of the elements included in the evaluation.
Assignments, along with selected topics from the course, form the basis for the oral exam. The external examiner will have the opportunity to see the answers to the assignments.
The re-examination is a oral examination assessed by the grade according to the 7-point grading scale and external co-examination.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
- Intro phase: 40 hours
- training phase: 30 hours
Note that part of the lectures will be given as video lectures. The participants will watch these and prepare themselves for dicussion about the topics in class.
Activities during the study phase:
- Self study of the teaching materials
- Solving weekly assignments in order to discuss these at the tutorials
- Written assignments as part of the exam
- Selfguided follow up on the intro and tutorial classes
- Repetition for the exam
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.