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

Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM527 or DM535 Discrete Methods for Computer Science must be known. The course cannot be followed if you have passed DM538, or if you have DM538 mandatory in your curriculum.

Course introduction
The course should give the students the skills to work with combinatorial mathematics and discrete probability, in particular their applications in computer science. In the first part of the course, the student will learn techniques for counting the number of elements in finite sets. In the second part, these techniques are used in conjunction with discrete probability spaces and distributions. Then we continue with more advanced counting techniques. The students will learn to use the principles above for developing and analyzing (randomized) algorithms, as well as applying randomization in the design of simple algorithms for e.g. graph connectivity. The course also contains an introduction to finite automata and their use in string matching problems.

Expected learning outcome
At the end of the course the student is expected to be able to:

• Apply the counting techniques from the course for finding the cardinality of a set.
• Apply the discrete probability techniques from the course, including analyzing central discrete probability distributions.
• Solve linear recurrence relations.
• Develop and analyze basic (randomized) algorithms using tools from combinatorics and discrete probability theory.
• Describe these actions in precise mathematical language, and argue for each of the steps of the calculations.
• Describe a finite automaton which corresponds to the string matching problem for a given text pattern P.
• Apply algorithms for finding occurences of a given text string in a text.
• Apply techniques from universal hashing to select hash function with good expected performance.

Subject overview
Combinatorics, counting techniques for permutations and combinations, binomial coefficients, the inclusion/exclusion principle, discrete probability theory, standard discrete probability distributions, recurrence relations, randomized algorithms, 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:
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. (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 Study phase: 30 hours

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.