SubjectsSubjects(version: 845)
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 to 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: http://iuuk.mff.cuni.cz/~sgall/vyuka/PALG/
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.

Course completion requirements - Czech
Last update: prof. RNDr. Jiří Sgall, DrSc. (26.02.2019)

Pro získání je zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru za podmínky účasti studenta na cvičeních. Při neúčasti jsou potřeba dvě třetiny z celkového počtu bodů. Povaha kontroly studia neumožňuje opakování zápočtu.

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.

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 | http://www.cuni.cz/UKEN-329.html