DM551: Algorithms and Probability

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

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

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

Odense

Show full time table

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Recommended course of study

Profile	Programme	Semester	Period

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.