Contents (hide)

Welcome to Randomized Algorithms homepage

Course Description

This course will explore techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas.

Some of the possible topics are:

  • Randomness in algorithms
  • The probabilistic method
  • Random walks and Markov chains
  • Randomization in approximation and online algorithms
  • Tail inequalities, Martingales

Course Schedule

Day Time Room
Wednesday 10:00-12:00Building 34, Room 209
Thursday14:00-16:00Building 90, Room 123


Name Web page E-mail Office Office hours
Ofer Neiman neimano at cs dot bgu dot ac dot il Building 37, Room 215 Thu. 10-12


  1. Randomized Algorithms, Motwani and Raghavan (1995).
  2. Probability and Computing, Mitzenmacher and Upfal (2005).

Grading Policy

Final exam, 70%.
Homework assignments, 30%. There will be 3 homework assignments.
You may hand in the exercises either by yourself or with one other student. Students whose partner has a valid reason not to hand in some assignment must still hand in the assignment. You may not hand in the assignments in groups larger than two. Cheating will not be tolerated.