# NDMI084 - Introduction to Approximation and Randomized Algorithms

This is the practical class for the lecture by doc. Kolman. The practicals take place every odd monday of the semester starting at 15:40 in S7. Information for the Czech practicals can be found here.

I recommend Design of Approximation Algorithms as a study material. Section 1.2 contains a relatively good introduction to linear programming.

## Conditions for passing the practicals

Over the course of the semester, three sets of homework will be given out. Thirty out of the sixty possible points will be needed for a pass. You will have at least two weeks to complete each set. Hand in your homework on paper or via email as a PDF.

## Homework

### Third set - Deadline 16.1.

I recommend handing this in before the holidays so you can enjoy them in peace.
##### Triangle removal - 9 points
You were given a convex polyhedron. Your task is to modify it into a similar-looking convex polyhedron that has no triangular faces. You are only permitted to add new faces of negligible dimensions (when compared to original faces) by truncating vertices. Come up with the best possible approximation algorithm for determining the minimal number of vertices to truncate.
##### Parallel max-4-cut - 13 points
Create a parallel approximation algorithm for max-4-cut. You have n⁴ processors at your disposal. The goal is to have a deterministic ¾-approximation in O(log n) worst-case time, but some points will be awarded for worse results. HINT: I would start with a randomized algorithm, but there are probably multiple ways to do this.

### Second set - Deadline 8.12.

Every task is worth 6 points.
##### Max k-cut
Given a graph, assign each vertex to one of k partitions such that as many edges as possible connect two vertices of different partitions. Find a deterministic (k-1)/k-approximation algorithm.

Hint: Start with randomized 2-cut. Partial points will be available for a randomized solution.
##### Ring network routing
Given a cycle of n computers connected in a ring topology network and a list of m messages to be sent from computer s_i to computer t_i (for i in 1,...,m), your task is to decide which direction should each message travel around the ring so that the number of messages using the most frequently used edge is as low as possible. Design a 2-approximation algorithm.
##### Quicksort
We have already seen that Quicksort runs in O(n log n) expected and O(n^2) worst-case time. Let us try and analyze Quicksort a little more carefully. Find an upper bound on the number of comparisons needed to sort n elements with probability at least 1-1/n.

### First set - Deadline 2.11.

Every task is worth 4 points.