Randomised Algorithms (RA)

Course content

Randomised algorithms are often far superior to their traditional deterministic counterparts, both in efficiency and simplicity. Many computational tasks are fundamentally impossible without randomisation. However, mastering randomised algorithms requires a basic mathematical understanding of the relevant combinatorial probability theory, and therefore a regular algorithms course will normally either skip them or teach them very superficially. Randomisation is a way of thinking, that needs a proper introduction. Applications in many areas will be considered, e.g., graph algorithms, machine learning, distributed computing, and geometry, but the focus will be on the general understanding, the goal being to give the students the foundation needed to understand and use randomisation, no matter what application area they may later be interested in.

Education

MSc Programme in Bioinformatics

MSc Programme in Computer Science

Learning outcome

Knowledge of

The relevant combinatorial probability theory and randomised techniques in algorithms:

  • Game-Theoretic Techniques
  • Moments and Deviations
  • Tail Inequalities
  • The Probabilistic Method
  • Randomised Data Structures
  • Randomised Geometric Algorithms
  • Randomised Graph Algorithms
  • Randomised Distributed and Parallel Algorithms


Skills in

  • Proving bounds on the expected running time of randomised algorithms
  • Explaining methods for bounding the probability that a random variable deviates far from its expectation
  • Applying the probabilistic method to prove the existence of e.g. algorithms
  • Giving algorithmic applications of random walks
  • Giving simple and efficient algorithms and data structures using randomisation where more traditional deterministic approaches are more cumbersome or less efficient


Competences to

  • Reason about and apply randomised techniques to computational problems that the student may later encounter in life.

 

Lectures and compulsory assignments.

See Absalon for a list of course literature.

The students should enjoy mathematics, as the course uses the power of
mathematics to understand and prove good performance of algorithms. It
is assumed that the students have completed an algorithms course such
as Advanced Algorithms and Data Structures, and are comfortable using
mathematical proofs in the analysis of algorithms.

Academic qualifications equivalent to a BSc degree is recommended.

This course has considerable overlap with the BSc-level course "Randomiserede algoritmer for dataanalyse". It is not recommended that you take this course if you have already taken the other. For details, contact the course organiser.

Written
Individual
Continuous feedback during the course of the semester
ECTS
7,5 ECTS
Type of assessment
Oral examination, 30 minutes (including grading)
The oral examination is with 30 minutes preparation,
Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners
Criteria for exam assessment

See Learning Outcome.

Single subject courses (day)

  • Category
  • Hours
  • Lectures
  • 36
  • Preparation
  • 85
  • Theory exercises
  • 84
  • Exam
  • 1
  • English
  • 206