Infopaket

Probabilistic Analysis of Algorithms

ДВС.3.06

Вибіркова дисципліна для ОП

First

2023/2024

8 Semester

6

LO 4. Be able to describe and analyze discrete objects and systems, using the concepts and methods of discrete mathematics and algorithm theory. LO 15. Be able to organize their own activities and get results within limited time. PLO 25.3. Be able to implement appropriate automated systems, operate them, performing the necessary calculations.

Full-time form

In order to successfully master the course "Probabilistic Analysis of Algorithms" the student must be fluent in the material of the standard courses "Programming", "Complex Analysis" and "Probability Theory". In particular, from the course "Programming" the student must know the basic sorting algorithms, search algorithms, basic algorithms on trees, as well as have basic skills in estimating the complexity of algorithms. From the course "Complex Analysis" the student must know the concept of an analytic function and singular points; be able to apply Cauchy's theorem and Cauchy's formula for analytic functions, derive Laurent and Taylor expansions, find residues. From the standard course "Probability Theory" the student must know the concept of a Markov chain, different types of convergence of random variables, the concept of characteristic function, be able to calculate the distributions and moments of random variables.

The classical analysis of algorithms focuses mainly on the study of average and extreme properties of computer algorithms. Probabilistic analysis of algorithms is a modern discipline that lies on the edge of probability theory and computer science, and is used to study more delicate characteristics of algorithms. During the course the student will get acquainted with the mathematical apparatus of this field, as well as with numerous applications, in particular, with probabilistic analysis of sorting algorithms, search algorithms, graph algorithms, compression algorithms and general algorithms of based on the "divide-and-conquer" paradigm.

1. Flajolet P., Sedgewick R. (2008). Analytic combinatorics, Cambridge University Press, 689 p. 2. Greene D. H., Knuth D.E. (1990). Mathematics for the analysis of algorithms, Birkhauser, 120 p. 3. Marynych A. (2010). On the asymptotics of moments of linear random recurrences. Theory Stoch. Proc. 16(32), pp. 106–119. 4. Graham, D. Knuth, D. And Patashnik, O. (1998). Concrete Mathematics. Addison-Wesley. 5. Whittaker E., Watson J. (1963). A course of modern analysis, Cambridge University Press. 6. Abramowitz M., Stegun, I. (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, 812 p. 7. Aczel J. (1966). Lectures on functional equations and their applications. Academic Press: New York, San Francisco, London, p. 530. 8. Marynych A. (2020). Probabilistic Analysis of Algorithms. https://do.csc.knu.ua/marynych/wp-content/uploads/sites/2/2023/11/PAA-EN.pdf

Lectures - 56 hours, consultations - 4 hours, slef-work - 120 hours. The course includes 4 content modules and 2 module tests. The discipline finishes with an exam in the 8th semester.

Intermediate assessment: The maximal number of available points is 60. • Test work no. 1: 30/18 points. • Test work no. 2: 30/18 points. Final assessment (in the form of exam): The maximal number of available points is 40. The form of exam: writing. The types of assignments are 4 writing assignments (2 theoretical and 2 practical).

Ukrainian