DM551: Algorithms and Probability (10 ECTS)

STADS: 15015901

Level
Bachelor course

Teaching period
The course is offered in the autumn semester.

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
The course cannot be chosen by students who have passed DM528 or DM538.

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

Subject overview
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
• Finite automata

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:

1. During the course two sets of problems are posed. The first of these has to be solved independently, while the second may be solved by groups of up to 3 persons. Together with selected topics from the course, these problem sets form the basis for an oral exam at the end of the course. The final grade, according to the 7-point grading scale, external examiner, will be based on an overall impression of the student's performance in the three elements which are part of the evaluation. The external examinator will be able to see the solutions of the two problem sets. (10 ECTS). (15015902).

Expected working hours
The teaching method is based on three phase model.
Intro phase: 40 hours
Skills training phase: 30 hours, hereof:
 - Tutorials: 30 hours

Educational activities
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

Educational form

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.