SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Randomized Algorithms - NDMI025
Title in English: Pravděpodobnostní algoritmy
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Guarantor: prof. RNDr. Jiří Sgall, DrSc.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: (11.05.2015)
The course covers the use of randomness in design of efficient algorithms. Use of randomness allows to solve problems more efficiently or even to solve problems that are otherwise intractable. The course covers techniques for design of randomized algorithm, demonstrated on concrete problems. We assume knowledge on the level of the courses NDMI084 Introduction to approximation and randomized algorithms and NTIN022 Probabilistic Techniques.
Aim of the course -
Last update: (11.05.2015)

Teach the students selected techniques of use of randomness in algorithms and of analysis of such algorithms.

Literature -
Last update: (11.05.2015)
  • M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
  • R. Motwani, P. Raghavan: Randomized algorithms. Cambridge Univ. Press, 1995.

Syllabus -
Last update: (11.05.2015)
  • Examples of randomized algorithms and protocols
  • Classes of languages defined by randomized algorithms and their relations
  • Minimax theorems (von Neumann, Yao)
  • Methods of derandomization: pairwise independent variables, expanders
  • Markov chains and their applications: random walks and connectivity, satisfiability algorithms, approximate counting (satisfying assignments, matchings in dense graphs), coupling (counting of graph colorings)
  • Introduction into queuing theory
  • Streaming algorithms
  • Randomized protocols and verification: linearity testing, PCP theorem (the proof of the exponential version)

Charles University | Information system of Charles University |