Velkommen til Københavns Universitets kursuskatalog
NDAK14005U Randomized Algorithms
Volume
2014/2015  Language  English   Credit  7,5 ECTS   Level  Full Degree Master   Duration  1 block   Placement  Block 2  Schedule  A (Tues 812 + Thurs 817)   Course capacity  No limit  Continuing and further
education   Study board  Study Board of Mathematics and Computer
Science   Contracting department   Department of Computer Science
  Course responsible   Mikkel Thorup (770776b7275787343676c316e7831676e)
  Saved on the
03122014 
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.  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
 Learning Outcome  Knowledge of: The relevant combinatorial
probability theory and randomized techniques in algorithms (see
course content).
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  Expected to be "Randomized Algorithms" by Motwani and
Raghavan  Teaching and learning methods  Lectures and compulsory
assignments 
Sign up  Self Service at KUnet

Exam  Credit  7,5 ECTS   Type of assessment  Oral examination, 30 minutter under invigilation 30 minutes preparation, 30 minutes oral examination, including
grade determination.   Exam registration requirements  The student must solve mandatory exercises during
the course. Assignments will be made each week and be due in the
following week. 5 out of 7 assignments must be completed by the due
date and approved to qualify to take the exam.   Aid  All aids allowed   Marking scale  7point grading scale   Censorship form  No external censorship
Several internal examiners    Criteria for exam assesment  See learning outcome. 

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

Saved on the
03122014

