NDAK14005U CHANGED: Randomized Algorithms (RA)

Volume 2018/2019
Education

MSc Programme in Computer Science

Content

Randomized algorithms are often far superior to their traditional deterministic counterparts, both in efficiency and simplicity. Many computational tasks are fundamentally impossible without randomization. However, mastering randomized 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. Randomization 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 randomization, no matter what application area they may later be interested in.

Learning Outcome

CHANGED FOR THE STUDY YEAR 2018/19

Knowledge of

The relevant combinatorial probability theory and randomized techniques in algorithms:

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


Skills in

  • Proving bounds on the expected running time of randomized 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 randomization where more traditional deterministic approaches are more cumbersome or less efficient


Competences to

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

 

Literature

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.
Lectures and compulsory assignments.
  • Category
  • Hours
  • Exam
  • 1
  • Lectures
  • 36
  • Preparation
  • 85
  • Theory exercises
  • 84
  • Total
  • 206
Written
Individual
Continuous feedback during the course of the semester
Credit
7,5 ECTS
Type of assessment
Oral examination, 30 minutes
30 minutes preparation, 30 minutes oral examination, including grade determination.
Exam registration requirements

The student must solve mandatory assignments during the course. Assignments will be made each week and be due in the following week. 5 out of 7 assignments must be submitted by the due date in order to qualify for the exam.

Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners
Re-exam

Re-exam same as ordinary exam.

If the student is not yet qualified, then qualification can be achieved by handing-in the missing assignments. The missing assignments must be submitted no later than two weeks before the re-exam date in order to qualify for the exam.

 

Criteria for exam assesment

See Learning Outcome.