Introduction to approximation and randomized algorithms

exercise sessions Wednesday 3:40PM S11 odd weeks of the semester (even calendar weeks)

Contact: mberg (at) kam.mff.cuni.cz

It is necessary to get at least half of the points from home assignments.
In case you wouldn't get the required amount of points from home assignments, it is possible to assign some additional exercises at the end of the semester.

16th October - exercise 1
30th October - No one came. You can try to solve these exercises at home. If you'd like to consult your solutions, you can contact me.
13th November
27th November
11th December

There will be 3 sets of home assignments during the semester. The deadline for submission of your solutions will be at least two weeks from the assignment of the set.
You can cooperate on solving the assignments with your colleagues. But please write the solution individually.
Please write your solutions in a clear and precise manner, try to justify all steps you are making in the solutions. You can use all claims from lectures and exercise sessions in the solutions, but always clarify, what exactly you are using.
It is possible to submit the solution by email to my address stated above or handwritten before the beginning of the exercise sessions.
Please choose your nickname and submit it together with the solutions of the first set of home assignments. Your results (number of points you got from each exercise in home assignments) will be posted here under your nickname.

4th November - first home assignment, deadline 27th November 11:59PM PLEASE NOTE: There was a minor error in exercise 2. There was "... all terminals F are in the same connected component ..." instead of "... all terminals R are in the same connected component ...". It's corrected now. I'm really sorry for the mistake and I hope it haven't confused you much.
11th December - second home assignment, deadline 12th January 11:59PM