SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Randomized Algorithms - NDMI025
Title: Pravděpodobnostní algoritmy
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: not taught
Language: English, Czech
Teaching methods: full-time
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
Is incompatible with: NTIN054, NDMX025
Is interchangeable with: NDMX025, NTIN054
Annotation -
Last update: IUUK (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: IUUK (11.05.2015)

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

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

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Literature -
Last update: IUUK (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.

Requirements to the exam -
Last update: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)

The exam is oral with time for written preparation. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Syllabus -
Last update: IUUK (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