Advanced Algorithms End Term: 31 August 2025, Set QDB3 (May 2025 term)

In this problem you are given as input a graph $T = (V, E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A perfect matching of $T$ is a subset $F \subset E$ of edges such that every vertex $v \in V$ is the endpoint of exactly one edge of $F$.

Equivalently, $F$ matches each vertex of $T$ with exactly one other vertex of $T$. For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it.

Algorithm A:

Algorithm B:

Is either algorithm correct?

Hint: Recall that every tree with at least two vertices has at least one degree one vertex.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

For n = 4, calculate the number of sequences of length 3 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

For n = 6, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Choose the correct options:

Consider the following instance of Set Cover problem:

• Universe $\mathcal{U} = \{a, b, c\}$
• Family $\mathcal{F} = \{S_1 = \{a, b\}, S_2 = \{a\}, S_3 = \{b\}, S_4 = \{c\}\}$

We build the following DP table for finding the Minimum Set Cover.

$\Pi(X, j)$ : minimum number of sets from $S_1, \ldots, S_j$ required to cover $X$

What is the missing entry?

Consider the following instance of Set Cover problem:

• Universe $\mathcal{U} = \{a, b, c, d\}$
• Family $\mathcal{F} = \left\{S_1 = \{a, c\}, S_2 = \{a, d\}, S_3 = \{b, d\}, S_4 = \{b, c\}\right\}$

We use dynamic programming to find the minimum number of sets from $\mathcal{F}$ required to cover $\mathcal{U}$. Recall that for every $X \subseteq \mathcal{U}$ and every $0 \leq j \leq |\mathcal{F}|$, our algorithm computes and stores $\Pi(X, j)$, i.e., minimum number of sets from $\mathcal{F}_j = \{S_1, \ldots, S_j\}$ required to cover $X$.

Consider the following DP table:

Based on the above data, answer the given subquestions.

Consider the following instance of Set Cover problem:

• Universe $\mathcal{U} = \{a, b, c, d\}$
• Family $\mathcal{F} = \left\{S_1 = \{a, c\}, S_2 = \{a, d\}, S_3 = \{b, d\}, S_4 = \{b, c\}\right\}$

We use dynamic programming to find the minimum number of sets from $\mathcal{F}$ required to cover $\mathcal{U}$. Recall that for every $X \subseteq \mathcal{U}$ and every $0 \leq j \leq |\mathcal{F}|$, our algorithm computes and stores $\Pi(X, j)$, i.e., minimum number of sets from $\mathcal{F}_j = \{S_1, \ldots, S_j\}$ required to cover $X$.

Consider the following DP table:

Based on the above data, answer the given subquestions.

In the MIN-2-SAT problem, we are given a 2-CNF formula $\phi$ and an integer $k$, and the objective is to decide whether there exists an assignment for $\phi$ that satisfies at most $k$ clauses.

Consider the following branching algorithm for the problem.

If there is a variable $x$ that occurs only positively in $\phi$, observe that there exists an optimal assignment that sets it to 0. Similarly, if there is a variable $x$ that occurs only positively in $\phi$, there exists an optimal assignment that sets it to 1. Once we perform this preprocessing, assuming that have clauses remaining, we have the following guarantee:

Every variable has at least one positive and one negated occurrence.

Now we can branch exhuastively on the settings of variables. The overall algorithm is summarized in the following pseudocode:

Which of the following statements is true?

Consider the given statements and answer the subquestions if they are true or false.

The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.

Consider the given statements and answer the subquestions if they are true or false.

An adversary can provide randomized quicksort with an input array of length $n$ that forces the algorithm to run in $\omega(n \lg n)$ time on that input.

(If you are not familiar with the $\omega$ asymptotic notation, it roughly translates as “at least”. For example, we can say that it is possible to come up with an input that forces insertion sort to run for $\omega(n^2)$ steps.)

Answer the given subquestions.

Every linear program has a unique optimal solution.

Answer the given subquestions.

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$, we have that $\{u, v\} \cap S$ is non-empty.

Consider the algorithm that repeats the following steps as long as the graph has at least one edge available: select a vertex of maximum degree (say $w$), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$.

Is it true that the algorithm always outputs a vertex cover?

Answer the given subquestions.

Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there examples of graphs where the size of the optimal vertex cover is exactly equal to twice the size of its maximum matching? For example, this is not true for a path on three vertices: the size of both the maximum matching and minimum vertex cover is 1

Consider the following approximation algorithm for the weighted vertex cover problem.

1: Solve the relaxed linear program corresponding to the given problem:

$\begin{aligned} &\text{Minimize} \quad && \textstyle\sum_{i=1}^{n} \mathit{weight}(v_i) \cdot x_i \\ &\text{Subject to} \quad && x_i + x_j \geq 1 \quad \text{for all edges } (v_i, v_j) \in E \\ & && 0 \leq x_i \leq 1 \quad \text{for } 1 \leq i \leq n \end{aligned}$

2: $C \leftarrow \{v_i \in V : x_i \geq 1/2\}$

3: return $C$

Based on the above data, answer the given subquestions.

Consider the following approximation algorithm for the weighted vertex cover problem.

1: Solve the relaxed linear program corresponding to the given problem:

$\begin{aligned} &\text{Minimize} \quad && \textstyle\sum_{i=1}^{n} \mathit{weight}(v_i) \cdot x_i \\ &\text{Subject to} \quad && x_i + x_j \geq 1 \quad \text{for all edges } (v_i, v_j) \in E \\ & && 0 \leq x_i \leq 1 \quad \text{for } 1 \leq i \leq n \end{aligned}$

2: $C \leftarrow \{v_i \in V : x_i \geq 1/2\}$

3: return $C$

Based on the above data, answer the given subquestions.