Probabilistic methods in computer science

2022/2023
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
A
ECTS:
6
Language:
slovenian, english
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)

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.

Readings

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.

Objectives and competences

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

Intended learning outcomes

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.

Learning and teaching methods

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

Assessment

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)

Lecturer's references

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]