Syllabus
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.
Annotation
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.