MSc:RandomizedAlgorithms

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

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%)