Advanced Seminar A (202-2-1511)

Randomized Algorithms

Fall 2009-2010

---

Announcements:

---

Instructor:

Matya Katz ( matya@cs.bgu.ac.il ) 

Office hours: Monday 12:00-14:00, Alon building (37), room 212, Tel: (08) 6461628

Class Time:

Tuesday 14-16 ( 34/116 )

---

Course Description:

Often a randomized algorithm is the simplest and fastest algorithm available. This course deals with the design and analysis of randomized algorithms. We will present basic tools from probability theory and probabilistic analysis that are used in the design and analysis of randomized algorithms, together with a large and diverse collection of applications, illustrating these tools.

---

Bibliography:

Main text book:

Randomized Algorthims

R. Motwani and P. Raghavan, Cambridge University Press, 1995

Additional text books:

Computational Geometry: Algorithms and Applications (3rd Edition)

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Springer-Verlag, 2008, ISBN: 978-3-540-77973-5

The probabilistic Method (3^rd Edition)

N. Alon and J.H. Spencer, Wiley, 2008

---

Requirements:

This is a 1-credit course.

Students are required to attend all lectures.

Each student will give a lecture. In addition several homework assignments and short quizzes are expected.

---

Student Presentations:

27.10.09 Michal and Rom (based on 1.1, 1.2, 1.3); presentation

03.11.09 Nova and Yael (based on 2.1, 3.1, 3.2, 3.3, 3.5-); p1, p2, p3

10.11.09 Igor and Nimrod (based on 4.1, 4.2, 4.3); p1, p2

17.11.09 Alex and Valery (based on 5.1, 5.2, 5.3-); p

24.11.09 Gabi and Gal (based on 8.1, 8.2, 8.3); p1, p2

01.12.09 Udi and Yigal (based on 10.1, 10.3); p1,p2

08.12.09 Achiya and Ran (based on 13.1, 13.2, 13.3, 13.4-, 13.5-, 13.6-); p

15.12.09 Amir and Erez (based on 9.1, 9.2, 9.3, 9.4); p

22.12.09 Lilach and Yoni (based on 9.8, 9.9, 9.10)

29.12.09 Nir (based on Welzl’s min enclosing circle paper)

Last update October 4, 2009.