NDAK14005U Randomized Algorithms
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
Knowledge of: The relevant combinatorial
probability theory and randomized techniques in algorithms (see
- 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.
Expected to be "Randomized Algorithms" by Motwani and Raghavan
- 7,5 ECTS
- Type of assessment
- Oral examination, 30 minutter under invigilation30 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.
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
Criteria for exam assesment
See learning outcome.
- Theory exercises