# 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

## 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

Student Identification Card

## 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

Name | Department | |
---|---|---|

Jørgen Bang-Jensen | jbj@imada.sdu.dk | Institut for Matematik og Datalogi, Datalogi |

## Timetable

## Administrative Unit

## Team at Educational Law & Registration

## 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.