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 2016/2017, which I will be attending -- and hopefully you as well!
The English exercise session takes place on Mondays at 14:00 in S6 (Malostranské náměstí, 1st floor) and the Czech exercise session on Mondays at 14:00 in S8. Each takes place only once every 14 days (they alternate).
The lecture is taught by Petr Kolman and Jiří Sgall, see the lecture's homepage.
For Czech-speaking students: V minulosti stačila stránka obou cvičení v angličtině. 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 practicals will consist of me showing how to solve a sample exercise on the board, as well easy-ish exercises for you so you can practice the techniques and get ready for the homework. We can also discuss lecture material if there was something unclear to you.
There is no mandatory attendance. The pass conditions can be found below.
If you miss one practical session in Czech, you can attend the English one (or vice versa). Still, please try and attend the practical session you have singed up to, so that the two sessions are balanced.
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 posted online 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.
There will be no points awarded at the regular classes and the consultations, but I still suggest you attend them to get more experience designing and analysing algorithms -- it will make the homework easier for you.
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.
- See other recommendations on the lecture website.
- 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.
Consultation sessions
In case you have missed something at the exercise session, at the lecture or you struggle with the homework, I have set up two consultation sessions for up to 5 people each. If you want to attend any of these, please sign up below, so I know you will be coming.
As always, I am available via email in case you get stuck or need any advice.
Lesson plan
- Class 1 (Czech, English): Introduction to approximation, vertex cover.
- Class 2 (Czech, English): Travelling salesman problem.
- Homework 1 (Czech, English).
- Class 3 (Czech, English): Intro to randomization.
- Class 4 (Czech, English): Greedy algorithms, SAT.
- Class 5 (Czech, English): Rounding of linear programs.
- Homework 2 (English).
- Class 6 (Czech, English): Paralelization.
- Homework 3 (English). Deadline: 30. 1. 2017 08:00.
Points
No points yet.