Exercise session for Introduction to approximation and randomized algorithms

Monday 15:40, S7, even semester weeks in winter 17/18

For the lecture Introduction to Approximation and Randomized Algorithms by doc. Petr Kolman and prof. Jiří Sgall I'm teaching an exercise session (also known as practicals or recitation sections).

For Czech students: Též jste vítáni na tomto cvičení. Ačkoliv bude hlavním jazykem angličtina, můžete se ptát v průběhu česky (např. pokud budete chtít něco přeložit z angličtiny). Stránky českého cvičení v úterý od 17:20 v liché týdny.

If you have any question, write to vesely (at) iuuk.mff.cuni.cz or ask after the exercise session. Also please do ask during the exercise session if you don't understand something. If you need a consultation, write me an email. For an idea about the exercise session look at the webpage of 2016 practicals by Martin Böhm.

What we have done

3. 10. Review of discrete probability and exercises to practise using it (Ex. 4.c will be done next time, ex. 5 is postponed to a later class).
23. 10. Simulating biased coin using a fair coin with only 2 flips in expectation. Travelling salesman problem exercises.
6. 11. Review of linear programming and integer linear programming for combinatorial problems. Exercises.
6. 11. Greedy algorithms for scheduling and knapsack. Exercises (the last exercise was finished next time, for the analysis of Ex. 4 you can look in book "The Design of Approximation Algorithms" (link below), Section 2.2).
4. 12. Rounding solutions of linear programs (relaxations). Exercises
18. 12. Taught by Pavel Dvořák: hashing (the last exercise will be finished next time). Exercises.
1. 1. No class, enjoy public holiday.
8. 1. 3-wise independent bits, and the size of the maximum matching via algebraic methods (precisely, we did the first exercise and the last exercise for both Edmonds and Tutte matrices). Exercises (the exercises about parallel algorithms are not hard, if you assume that you can find a maximal independent set in a graph and sort numbers fast with many processors)

Homeworks

Study materials (by Martin Böhm)

Some supplementary reading:

Pass conditions

To get a pass ("zápočet") you need at least the half of total points for homeworks. During the semester I will post three homework sets with 4 exercises, each worth approx. 4-6 points, on this webpage. To solve the homeworks you will have at least 14 days. Additionally, you can get points for bonus exercises (inside the homework sets) which do not count in the limit of total points per semester. Also, you may be awarded some points for showing a solution of an exercise during the class (at most 2 points per an exercise).

In your solutions try to properly explain every step. On the other hand, you can use everything from the lecture or the exercise session without a proof, you just need to mention what you are using. You can cooperate on the solutions, however, it is important that you understand the solution thoroughly and you have to write your solution by yourself. Points assigned to exercises do not necessarily reflect their difficulty.

Send me your solutions preferably to my email address at the top of the page (in PDF, ODT ... or just inside the email). I also accpet scans or photos of quality high-enough to read everything without problems. Another possibility is to hand your solutions in on a paper at the beginning of a class.

Attendance on classes is not mandatory, though highly recommended in order to understand the lectures better.

Table of points

In the table you can find your initials (in the reverse order, that is, SF for a student Surname Forename), but you can choose a nickname. Notation x.y means "Homework set x, exercise y" and Sx is the sum of points for the homework set x. Question mark means that the solution needs an explanation.