There are no prerequisites.
Probabilistic methods in computer science
2021/2022
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
Lecturers:
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]
