There are no prerequisites.

# Probabilistic methods in computer science

Quicksort and minimum cut.

Classes of problems and types of randomized algorithms.

Use of polynomials.

Chernoff bounds.

Randomized incremental constructions and backwards analysis.

Linear programming in low dimensions.

Markov chains.

Approximate counting.

Sublinear algorithms.

Probabilistic method.

M. Mitzenmacher in E. Upfal. Probability and Computing. Cambridge University Press, 2005.

R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. 3. izdaja, Springer, 2008.

J. Kleinberg in É. Tardos. Algorithm Design. Addison-Wesley, 2005.

Student gets acquainted with the use of probability for algoritmic and related problems.

Basic randomized algorithms.

Randomized algorithms in computational geometry.

Using probability to analize the running time of algorithms.

Use of probability to show existance of objects.

Lectures, seminar, exercises, homework, consultations, and independent work by the students.

Exercise-based exam (2 midterm exams or written exam) or homework

Oral exam

Grading: 6-10 pass, 5 fail (according to the rules of University of Ljubljana)

CABELLO, Sergio, ROTE, Günter. Obnoxious centers in graphs. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 4, str. 1713-1730. [COBISS-SI-ID 15762265]

BERG, Mark de, CABELLO, Sergio, HAR-PELED, Sariel. Covering many or few points with unit disks. Theory of computing systems, ISSN 1432-4350, 2009, vol. 45, no. 3, str. 446-469. [COBISS-SI-ID 14900825]

CABELLO, Sergio, FORT, Marta, SELLARÈS, J. Antoni. Higher-order Voronoi diagrams on triangulated surfaces. Information processing letters, ISSN 0020-0190. [Print ed.], 2009, vol. 109, iss. 9, str. 440-445. [COBISS-SI-ID 15160153]