Kursussøgning, efter- og videreuddannelse – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Kursussøgning, efter- og videreuddannelse

Randomized Algorithms (RA)

Practical information
Study year 2016/2017
Time
Block 4
Programme level Full Degree Master
ECTS 7,5 ECTS
Course responsible
  • Mikkel Thorup (7-757c70777a7d78486c7136737d366c73)
  • Department of Computer Science
Course number: NDAK14005U

Course 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 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

Knowledge of:

The relevant combinatorial probability theory and randomized techniques in algorithms:

  • Game Theoretic Techniques
  • Moments and Deviations
  • Tail Inequalities
  • The Probabilistic Method
  • Markov Chains and Random Walks
  • 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.

 

Recommended prerequisites

Students are assumed to have a basic understanding of Algorithms and Data Structures, e.g., from the bachelor course of this name. Students should also enjoy getting a mathematical understanding of algorithms.

Sign up

As an exchange, guest and credit student - click here!

Continuing Education - click   here!

Education

MSc programme in Computer Science

Studyboard

Study Board of Mathematics and Computer Science

Course type

Single subject courses (day)

Duration

1 block

Schedulegroup

A
---- SKEMA LINK ----

Teaching and learning methods

Lectures and compulsory assignments

Capacity

No limit

Language

English

Literature

Expected to be "Randomized Algorithms" by Motwani and Raghavan

Workload

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

Exam

Type of assessment

Oral examination, 30 minutes
30 minutes preparation, 30 minutes oral examination, including grade determination.

Aid

All aids allowed

Marking scale

7-point grading scale

Criteria for exam assessment

See learning outcome.

Censorship form

No external censorship
Several internal examiners

Re-exam

If student is not qualified then qualification can be achieved by hand-in and approval of equivalent exercises.

Re-exam same as ordinary exam.

Mere information om kurset
Er du BA- eller KA-studerende?
Er du bachelor- eller kandidat-studerende, så find dette kursus i kursusbasen for studerende:

Kursusinformation for indskrevne studerende