SubjectsSubjects(version: 941)
Course, academic year 2022/2023
   Login via CAS
Probabilistic Analysis of Algorithms - NTIN018
Title: Pravděpodobnostní analýza algoritmů
Guaranteed by: Department of Distributed and Dependable Systems (32-KDSS)
Faculty: Faculty of Mathematics and Physics
Actual: from 2014
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information:
Guarantor: RNDr. Alena Koubková, CSc.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: Tajemník Katedry (22.04.2010)
An illustration of using probabilistic methods in analysis of the expected running time of deterministic algorithms (e.g. sorting, graphs algorithms) and in the construction and analysis of randomized algorithms. Basic knowledge of statistics is required.
Literature - Czech
Last update: KOUBKOVA/MFF.CUNI.CZ (15.05.2008)

Feller, W.: An introduction to probability theory and its applications.Wiley, New York,1970.

Hofri, M.: Probabilistic analysis of algorithms. Springer-Verlag, 1987.

Sedgewick, R., Flajolet, P.: An introduction to the analysis of algorithms. Addison-Wesley, 1996.

Requirements to the exam - Czech
Last update: RNDr. Alena Koubková, CSc. (10.10.2017)

Zkouška má pouze ústní část. Požadavky odpovídají sylabu předmětu.

Syllabus -
Last update: T_KSI (24.05.2002)

The worst case and average case time complexity of algorithms. Methods for computing of the expected running time of deterministic algorithms under known distribution of input data (straight computing, using generating functions, recurrences).

Higher order moments of running time, the variance. Markov's inequality, Chebyshev's inequality, their importance for estimation of probability of large deviations from the expected running time.

The representation of an algorithm by a Markov chain, transition probabilities between the states of computing, the expected number of passes through given states.

The principle and importance of randomized (probabilistic) algorithms. Computing of their expected time complexity, estimation of the error probability.

Examples of probabilistic analysis of algorithms: simple counting on the Turing machine, finding the largest term in a sequence, sorting algorithms (Selectionsort, Quicksort, Insertinsort, Shellsort), graph algorithms (graph coloring, transitive closure, random walks on graphs), probabilistic primality testing, randomized SAT and others.

Charles University | Information system of Charles University |