Randomization in algorithms and computational geometry 1000-2M20RGO
i. Basic probabilistic concepts: probability space, random variables, independence; Introduction to Probabilistic Combinatorics; Some examples (1 lecture).
ii. Lovász Local Lemma and Algorithmic Applications (2 lectures).
iii. Random Graphs (2 lectures).
iv. Power of choice, 2 methods (1 lecture).
v. Randomized rounding (1 lecture).
vi. Range spaces and ε-nets (1 lecture).
vii. Range search; Point location (1 lectures).
viii. Metric embeddings and dimensionality reduction (2 lectures).
ix. Markov chains and random walks on graphs (1 lecture).
x. Schöning’s k-SAT algorithm (1 lecture).
xi. Graph sparsification (1 lecture).
xii. Convex Polytopes (1 lecture).
Type of course
Ph. D. seminars
Mode
Prerequisites (description)
Course coordinators
Learning outcomes
Knowledge:
* Knowledge of basic and some advanced probabilistic methods used in computer science.
* A reasonably wide exposure to classic and modern algorithmic problems.
* Understanding the importance of mathematical proofs.
Skills:
* Ability to apply probabilistic concepts to the analysis of algorithms.
* Ability to select appropriate probabilistic tools, or to tweak existing tools if required, to solve algorithmic or combinatorial problems.
Competence:
* Awareness of own limitations and the need for further study.
* Development of the ability to read scientific articles, if necessary in a foreign language, to expand their knowledge.
* Ability to precisely formulate questions to deepen their own understanding or to find gaps in reasoning.
For PhD students, they know (i) the development trends in their field against the background of other natural and exact sciences, as well as the related dilemmas of the modern civilisation, (ii) their discipline-specific achievements at the level allowing for its creative development and the research methodology in their discipline, (iii) how to make use of the sources (books, articles, etc.) that present the results in their discipline, also in a foreign language, (iv) are able to present advanced ideas and results in their discipline, and are able to organise self-education in their discipline, and (v) are ready to undertake the task of a researcher in the society.
Assessment criteria
There will be 2-3 graded homework assignments. Students getting at least 50 percent grades in the homework, will be eligible to appear for the main exam.
The main exam will be a take-home exam, followed by a short oral.
The final grade will be 50% of the aggregate of the homework grades and 50% of the main exam.
PhD students have the option to either (a) present a paper from a list of selected recent papers, OR (b) solve a challenging (starred) homework problem, preparing for research work.
Bibliography
* Alon and Spencer, The Probabilistic Method.
* Motwani and Raghavan, Randomized Algorithms.
* Mitzenmacher and Upfal, Probability and Computing.
* Feller, An Introduction to Probability Theory and Its Applications, Part I.
* Selected recent papers.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: