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

The course has joined classes with MM851.

Entry requirements

The course cannot be chosen by students who have passed MM541, DM538 or DM551/MM851.

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

See itslearning for syllabus lists and additional literature references.

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

70 hours per semester

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 E-mail Department
Jørgen Bang-Jensen jbj@imada.sdu.dk Institut for Matematik og Datalogi, Datalogi

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

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.