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

• First homework set – till Monday November 20, 2017 15:39. Solutions of ex. 2-4.
• Second homework set – till Tuesday December 19, 2017 (there was a mistake in Ex. 1, correction is highlighted bold). Be aware that in the 3rd exercise the numbers need not be different.
• Third homework set – till Sunday February 4, 2018 (if you are too busy during the exam period and you miss just a few points, let me know and we will agree on finishing the credit for this class). "A fast randomized parallel algorithm" means an algorithm running in (expected) polylogarithmic time on polynomial processors. If you miss a few points after solving the third HW set (but not necessarily the bonus exercise), let me know and I will give you another exercise to solve.

Study materials (by Martin Böhm)

• The Design of Approximation Algorithms (David P. Williamson, David B. Shmoys). An excellent textbook on approximation algorithms. Self-contained, although I recommend consulting some other textbooks if you need to learn the basics, such as linear programming. Contains a lot of advanced techniques later on -- we will focus on the basics. Can be downloaded from the above website.
• See other recommendations on the lecture website.
• Review of probability in discrete mathematics by Jiří Matoušek.
• For Czech students: there are work-in-progress lecture notes in Czech by Jiří Sgall.

Some supplementary reading:

• Understanding and Using Linear Programming (Jiří Matoušek, Bernd Gärtner). An introductory book to Linear Programming for computer scientists. If you want to brush up on linear programming, this might come in handy.

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.