Randomized Algorithms

Course name: Randomized Algorithms
Course number: DS-07
Area of instruction: Computer Science and Engineering

Administrative details

Faculty: Computer Science and Engineering
Year of instruction: 1st year of MSc
Semester of instruction: 2nd semester
No. of Credits: 5 ECTS
Total workload on average: 180 hours overall
Frontal lecture hours: 2 hours per week.
Frontal tutorial hours: 0 hours per week.
Lab hours: 2 hours per week.
Individual lab hours: 2 hours per week.
Frequency: weekly throughout the semester.
Grading mode: letters: A, B, C, D.

Course outline

This course covers basic concepts in the design and analysis of randomized algorithms focusing on statistical techniques used in science and industry. The goal of the course is to show the power of randomized algorithms and its applications. Topics include: Hypothesis testing and estimation, game theoretic techniques, graph algorithms, non-parametric statistics, analysis of variance, decision theory, and Bayesian statistics.

Expected learning outcomes

Students are able to measure randomness of given algorithms.
Students can predict how the randomness affects behaviors of algorithms.
Students can derandomize algorithms, i.e., extract deterministic instances.

Required background knowledge

Solid knowledge of data structures and algorithms, number theory, and good programming skills are assumed.

Prerequisite courses

It is recommended to pass Advanced Statistics course before Randomized Algorithms course to be familiar with probability and statistics.

Detailed topics covered in the course

Introduction to Randomized Algorithms
Game Theoretic Techniques
Moments and Deviations
Tail Inequalities
The Probabilistic Method
Markov Chains and Random Walks
Algebraic Techniques
Data Structures
Geometric Algorithms and Linear Programming
Graph Algorithms
Approximate Counting

Textbook

Reference material

Mathematical Statistics and Data Analysis by John A. Rice

Required computer resources

Students should have laptops and access to the textbook.

Evaluation

Assignments (20%)
Project (30%)
Midterm Exam (30%)
Quizzes (15%)
Course Participation (5%)

MSc:RandomizedAlgorithms

Contents