Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Introduction to Approximation and Randomized Algorithms - NDMI084

Title:	Úvod do aproximačních a pravděpodobnostních algoritmů
Guaranteed by:	Computer Science Institute of Charles University (32-IUUK)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2020
Semester:	winter
E-Credits:	5
Hours per week, examination:	winter s.:2/1, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time
Additional information:	https://iuuk.mff.cuni.cz/~sgall/vyuka/BCALG/

Guarantor:	prof. RNDr. Jiří Sgall, DrSc. doc. Mgr. Petr Kolman, Ph.D.
Class:	Informatika Bc.
Classification:	Informatics > Optimalization

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

Last update: RNDr. Ondřej Pangrác, Ph.D. (14.02.2018)

This course covers techniques for design and analysis of algorithms, demonstrated on concrete combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design algorithms that find an optimal solution fast. In such a case we study approximation algorithms that work faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness in design of algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable. Recommended for the 3rd year of Bc. studies.

Course completion requirements -

Last update: doc. Mgr. Petr Kolman, Ph.D. (29.09.2020)

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester. Due to the requirements, additional attempts to pass the tutorial are excluded.

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam. If university attendance is limited, the exam may be held online.

Literature -

Last update: G_I (28.05.2012)

D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.

J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.

V.V. Vazirani: Approximation Algorithms, Springer, 2001.

R. Motwani, P. Raghavan: Randomized algorithms.

M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis.

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: doc. Mgr. Petr Kolman, Ph.D. (29.09.2020)

Detailed information about the course are given at the web page https://kam.mff.cuni.cz/~kolman/intapxalg.html .

Here is a list of the main topics.

Covered techniques:

Greedy algorithms as a design method for approximation and online algorithms

Use of linear programming for approximation algorithms

Pairwise independent random variables

Derandomization using the conditional expectations technique

Local search

Covered problems and algorithms:

scheduling and disjoint paths in graphs - greedy algorithms

travelling salesperson problem - combinatorial algorithms

set cover - greedy algorithm, use of linear programming

satisfiability (MAX-SAT) - use of linear programming, randomized rounding, derandomization

dynamic and static hashing - randomized algorithms, pairwise independent variables

maximal cut - approximation using local search

minimal cut - a fast randomized algorithm

maximal independent set - a fast randomized parallel algorithm

verification of matrix equation - a randomized protocol