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.
MSc Programme in Bioinformatics
MSc Programme in Computer Science
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 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. In addition,
some basic
knowledge of discrete probability theory is assumed, e.g. what is a
discrete
random variable, what is expectation, etc.
Academic qualifications equivalent to a BSc degree is
recommended.
As an exchange, guest and credit student - click here!
Continuing Education - click here!
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- ECTS
- 7,5 ECTS
- Type of assessment
-
Oral examination, 30 minutes (including grading)
- Type of assessment details
- The oral examination is with 30 minutes preparation,
- 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. 4 out of 6 assignments must be submitted and approved 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
-
Same as ordinary exam.
If the student is not yet qualified, then qualification can be achieved by submitting 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 re-exam.
Criteria for exam assessment
See Learning Outcome.
Single subject courses (day)
- Category
- Hours
- Lectures
- 36
- Preparation
- 85
- Theory exercises
- 84
- Exam
- 1
- English
- 206
Kursusinformation
- Language
- English
- Course number
- NDAK14005U
- ECTS
- 7,5 ECTS
- Programme level
- Full Degree Master
- Duration
-
1 block
- Placement
- Block 4
- Schedulegroup
-
B
- Capacity
- No limitation – unless you register in the late-registration period (BSc and MSc) or as a credit or single subject student.
- Studyboard
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Contracting faculty
- Faculty of Science
Course Coordinator
- Jacob Holm (4-6d646b7243676c316e7831676e)
Er du BA- eller KA-studerende?
Kursusinformation for indskrevne studerende