This is the website for the Practicals (also known as exercise sessions or recitation sections) of the lecture "Introduction to Approximation and Randomized Algorithms" in the winter semester 2015/2016, which I will be attending -- and hopefully you as well!
The exercise session starts at 17:20 in S7 (Malostranské náměstí, 1st floor).
The lecture is taught by professor Sgall.
For Czech-speaking students: zatím se zdá, že tato stránka postačuje v angličtině. Necham ji tedy tak. Pokud kdokoli z vás by ocenil tuto stránku přeloženou do češtiny, dejte mi prosím vědět a já českou variantu zavedu.
Structure of the practical
The regular practicals will take place every even week at 17:20 at S7, starting on 13. 10. 2015. After discussing it with the lecturer, we have decided to make the regular practicals in Czech. The practicals will consist of me showing how to solve a sample exercises on the board, as well easy-ish exercises for you so you can practice the techniques and get ready for the homework.
The English consultations will take place every odd week on Wednesdays at 17:20, starting with the 3rd week, in the 3rd floor corridor of KAM/IUUK (the corridor opposite S3). They will be roughly equivalent to the regular practicals, except they will have a looser structure and we can tailor them more to the individual students' needs (discussing lecture material, more advanced exercises and such).
You can choose to attend the English consultation or the regular practical as you please. In fact, there is no mandatory attendance. The pass conditions can be found below.
Pass conditions
To get a pass from the practical, you will need to reach at least 50% of the homework point limit. I expect the point limit to be 24 points, so you will likely need at least 12 points.
There will be 3 homework sets each with about 4 exercises worth 2 points each. There will be at least 14 days to solve each set. After the deadline, the solutions to the homework set will be posted online.
There may also be bonus exercises in each homework set. They can be solved just like the standard homework (and you will get points for them), but they do not contribute to the point limit.
To make things fair for English and Czech students alike, there will be no points awarded at the regular classes and the consultations.
Study materials
- 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.
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.
Lesson plan
- Class 1 (English, Czech): TSP and its many variants.
- 19.10.: First homework: English, Czech. A small typo was fixed in task 4. Solutions.
- Class 2 (English, Czech): Intro to randomness in CS: cards and clauses.
- Class 3 (English, Czech): greed, cuts and SAT. Czech solution of the first two exercises.
- 24.11.: Second homework: English, Czech. Solutions.
- Class 4 (English, Czech): set cover, centers and leftovers.
- 31.12.: Third homework: English, Czech.
- Update: Tuesday 19.1.2016 17:19: Deadline of the third homework set.