DM839: Randomized algorithms (10 ECTS)

STADS: 15014701

Level
Master's level course approved as PhD course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: jbj@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal. 3. +4. kvartal.

Prerequisites:
None

Academic preconditions:
Knowledge about algorithms, data structures, complexity and discrete probability theory corresponding to e.g. DM507, DM508 and DM538

Course introduction
Probabilistic analysis of algorithms, randomized algorithms and probabilistic combinatorial constructions have become fundamental tools for computer science and applied mathematics. The purpose of the course is to give a solid foundation for applications of discrete probability as a tool for analysis, as well as design of algorithms. This includes illustrations of the probabilistic method as a tool to develop randomized algorithms. The course contains both theoretical and practical (experimental) elements and these are weighted equaly.

Qualifications
The students will gain detailed knowledge about applications of randomization and elementary probability theory in the design and analysis of algorithms and after the course they are expected to  be able to apply the obtained knowledge, where relevant to

• analyze the expected running time of certain deterministic algorithms
• design new randomized algorithms for problems similar to those studied in the course.
• apply randomization as a tool for developing deterministic algorithms through the use of derandomization techniques.
• estimate the expected running time of Las Vegas algorithms
• estimate the probability of a correct answer by a Monte Carlo algorithm
• apply the probabilitic method to problems similar to those studied in the course.
• use randomization as a tool for developing protocols for e.g. communication problems

Expected learning outcome


Subject overview
development of randomized algorithms (example: min cut in graphs), expected running time of algorithms, error probability of algorithms, the probabilistic method, Chernoff bounds, Hashing, derandomization, balls in bins and random graphs, experimental testing of (randomized algorithms), etc.     

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam based on project and assignments. External examiner, graded after Danish 7 mark scale (10 ECTS)

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

Educational activities Study phase: 60 hours

Language
This course is taught in English, if international students participate. Otherwise the course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.