Welcome to Randomized Algorithms homepage
Course DescriptionThis 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
|Wednesday||10:00-12:00||Building 34, Room 209|
|Thursday||14:00-16:00||Building 90, Room 123|
|Name||Web page||Office||Office hours|
|Ofer Neiman||http://www.cs.bgu.ac.il/~neimano||neimano at cs dot bgu dot ac dot il||Building 37, Room 215||Thu. 10-12|
- Randomized Algorithms, Motwani and Raghavan (1995).
- Probability and Computing, Mitzenmacher and Upfal (2005).
Grading PolicyFinal 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.