July 1st, 2025

Efficient Algorithms exam topics from 1 July 2025. This is a reconstruction; some task descriptions and answer options are missing.

1. Bicoloured Subset Sum

Bicoloured Subset Sum

Input: A multiset $P$ of numbers, each coloured either red or blue, and a target integer $t$.

Question: Does there exist a submultiset $S\subseteq P$ such that ${\sum }_{p\in S}p=t$ and $S$ contains equally many red and blue numbers? Here, selection is by occurrence, rather than by distinct value as in an ordinary subset.

(a) Describe a dynamic programming algorithm solving this problem.

(b) Give a running-time bound in $\mathcal{O}$-notation.

2. Exponential-Time Algorithms and ETH

Task

(a) For the 5-Colouring problem, there is a trivial branching algorithm with running time $\mathcal{O}(5^n\cdot n^{\mathcal{O}(1)})$. Give an improved single-exponential algorithm with running time $\mathcal{O}(c^n\cdot n^{\mathcal{O}(1)})$, where $c<5$.

(b) Assume that there is a linear-time reduction from 3-SAT to another problem. Which of the listed running times can be excluded under the Exponential Time Hypothesis? You do not have to justify your answer.

The four running-time options are missing from the reconstruction.

3. Minimum Vertex Cover Approximation

Task

Two algorithms for Minimum Vertex Cover were described. Decide which one is a factor-2 approximation algorithm and prove its approximation guarantee.

The algorithm descriptions are missing from the reconstruction.

4. Chamberlin–Courant Rule and Integer Linear Programming

Task

The task included a description of the Chamberlin–Courant (CC) voting rule and asked for a committee of size $k$ with maximum CC score. Complete the partial integer linear programming (ILP) formulation by filling in the parts marked with question marks.

Let $V=\{v_1,\dots ,v_n\}$ be the voters and $\{c_1,\dots ,c_m\}$ the alternatives. The binary variable $x_i$ indicates whether voter $v_i$ is represented, and $y_j$ indicates whether alternative $c_j$ belongs to the committee.

$$\begin{array}{rlrl}\text{maximise}& ?& & \\ \text{subject to}& ?\le ?& & \forall v_i\in V,\\ & ?=?,& & \\ & x_i\in \{0,1\}& & i\in \{1,\dots ,n\},\\ & y_j\in \{0,1\}& & j\in \{1,\dots ,m\}.\end{array}$$

Additional multiple-choice questions concerned the running time of ILP algorithms.

The precise voting-rule description and the multiple-choice options are missing from the reconstruction.

5. Condorcet Winners and Kemeny Consensus

Task

Prove the following statement:

A Condorcet winner $x$ comes first in every Kemeny consensus ranking.

6. Single-Machine Scheduling

Task

Give a polynomial-time algorithm that solves $1\mid \mid L_{\max }$ optimally. If your algorithm differs from the one presented in the lecture, also prove its correctness.

Additional multiple-choice questions concerned the complexity of $1\mid r_j\mid L_{\max }$.

7. Matroids and Max-2-SAT

Task

Two sets of multiple-choice questions concerned:

• Matroids: circuits and the number of independent sets given $k$ bases of cardinality $n$.
• Max-2-SAT: fully polynomial-time approximation schemes (FPTAS), pseudo-polynomial algorithms, and related topics.

The exact questions and answer options are missing from the reconstruction.