During the course, you will find here the documents for the theoretical and practical exercises as well as the corresponding solutions.
It is suggested that the implementations of the exercises are done in python (recommended, though MATLAB is also accepted). If you want to install python, it is probably the easiest to use the free Anaconda python distribution. The distribution is available on Linux, Mac, and Windows and some of the advantages are listed here. Please make sure that you successfully installed python (or MATLAB) before the first lecture in order to increase the time you have for the actual exercise.
In the lecture, we have introduced the general concept of polynomial reductions to prove the NP-completeness of decision problems. It is the purpose of this exercise to prove two more polynomial reductions between other optimization problems. On the one hand, we will polynomially reduce the (undirected) HAMILTONIAN CIRCUIT (HC) problem to the TRAVELING SALESPERSON PROBLEM (TSP) and, on the other hand, we will polynomially reduce VERTEX COVER to CLIQUE.
In the lecture, the general concept of greedy algorithms has been introduced in which locally optimal choices are made. In this exercise, we apply this idea to the knapsack problem. We are not only going to formally define the algorithm but also to implement it.
In the lecture, we have seen the general concept of dynamic programming and it is the purpose of this exercise to apply it to the knapsack problem. We are going to not only formally define the algorithm but also implement it.
In the lecture, we have seen the general idea of numerical optimization algorithms, following decent directions and a few concrete examples of decent directions as well as line search variants. Here, we will have a closer look on their performance on specific convex quadratic functions of the form f(x) = xTAx.