Advanced Algorithms Quiz 2: 3 December 2023 (September 2023 term)

You are given a sequence of integers $a$ of length $2n$. You have to split these $2n$ integers into $n$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $a$ should become the $x$ or $y$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $s$ that starts from one of these points, ends at one of these points, and visits all $n$ points at least once.

The length of path $s$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Your task is to form $n$ points and choose a path $s$ in such a way that the length of path $s$ is minimized.

For example, if the given sequence is 15, 1, 10, 5, then you can form points $(10, 1)$ and $(15, 5)$ and start the path $s$ from the first point and end it at the second point. Then the length of the path will be $|10 - 15| + |1 - 5| = 5 + 4 = 9$. It can be shown that this is the best possible.

Based on the above data, answer the given subquestions.

You are given a sequence of integers $a$ of length $2n$. You have to split these $2n$ integers into $n$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $a$ should become the $x$ or $y$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $s$ that starts from one of these points, ends at one of these points, and visits all $n$ points at least once.

The length of path $s$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Your task is to form $n$ points and choose a path $s$ in such a way that the length of path $s$ is minimized.

For example, if the given sequence is 15, 1, 10, 5, then you can form points $(10, 1)$ and $(15, 5)$ and start the path $s$ from the first point and end it at the second point. Then the length of the path will be $|10 - 15| + |1 - 5| = 5 + 4 = 9$. It can be shown that this is the best possible.

Based on the above data, answer the given subquestions.

You are given a sequence of integers $a$ of length $2n$. You have to split these $2n$ integers into $n$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $a$ should become the $x$ or $y$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $s$ that starts from one of these points, ends at one of these points, and visits all $n$ points at least once.

The length of path $s$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Your task is to form $n$ points and choose a path $s$ in such a way that the length of path $s$ is minimized.

For example, if the given sequence is 15, 1, 10, 5, then you can form points $(10, 1)$ and $(15, 5)$ and start the path $s$ from the first point and end it at the second point. Then the length of the path will be $|10 - 15| + |1 - 5| = 5 + 4 = 9$. It can be shown that this is the best possible.

Based on the above data, answer the given subquestions.

You are given a sequence of integers $a$ of length $2n$. You have to split these $2n$ integers into $n$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $a$ should become the $x$ or $y$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $s$ that starts from one of these points, ends at one of these points, and visits all $n$ points at least once.

The length of path $s$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Your task is to form $n$ points and choose a path $s$ in such a way that the length of path $s$ is minimized.

For example, if the given sequence is 15, 1, 10, 5, then you can form points $(10, 1)$ and $(15, 5)$ and start the path $s$ from the first point and end it at the second point. Then the length of the path will be $|10 - 15| + |1 - 5| = 5 + 4 = 9$. It can be shown that this is the best possible.

Based on the above data, answer the given subquestions.

Let $a_1, \ldots, a_{2n}$ be the input sequence in sorted (ascending) order. In particular, the minimum element is $a_1$, the maximum element is $a_{2n}$, and the element $a_n$ is at least as large as the first $n - 1$ elements, and $a_{n+1}$ is at most the value of the last $n - 1$ elements. No matter how we form the points as described in the problem, the resulting path will have a length of at least:

You are given a sequence of integers $a$ of length $2n$. You have to split these $2n$ integers into $n$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $a$ should become the $x$ or $y$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $s$ that starts from one of these points, ends at one of these points, and visits all $n$ points at least once.

The length of path $s$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Your task is to form $n$ points and choose a path $s$ in such a way that the length of path $s$ is minimized.

For example, if the given sequence is 15, 1, 10, 5, then you can form points $(10, 1)$ and $(15, 5)$ and start the path $s$ from the first point and end it at the second point. Then the length of the path will be $|10 - 15| + |1 - 5| = 5 + 4 = 9$. It can be shown that this is the best possible.

Based on the above data, answer the given subquestions.

Tina stumbles upon a lottery chart dropped by a time traveler from the future, which lists winning lottery numbers and positive integer cash payouts for the next $n$ days. Tina wants to use this information to make money, but is worried if she plays winning numbers every day, lottery organizers will get suspicious. As such, she decides to play the lottery infrequently: at most twice in any seven day period.

In this problem, we will build up towards an $O(n)$-time algorithm to determine the maximum amount of lottery winnings Tina can win in the next $n$ days by playing the lottery infrequently.

Based on the above data, answer the given subquestions.

Tina stumbles upon a lottery chart dropped by a time traveler from the future, which lists winning lottery numbers and positive integer cash payouts for the next $n$ days. Tina wants to use this information to make money, but is worried if she plays winning numbers every day, lottery organizers will get suspicious. As such, she decides to play the lottery infrequently: at most twice in any seven day period.

In this problem, we will build up towards an $O(n)$-time algorithm to determine the maximum amount of lottery winnings Tina can win in the next $n$ days by playing the lottery infrequently.

Based on the above data, answer the given subquestions.

Tina stumbles upon a lottery chart dropped by a time traveler from the future, which lists winning lottery numbers and positive integer cash payouts for the next $n$ days. Tina wants to use this information to make money, but is worried if she plays winning numbers every day, lottery organizers will get suspicious. As such, she decides to play the lottery infrequently: at most twice in any seven day period.

In this problem, we will build up towards an $O(n)$-time algorithm to determine the maximum amount of lottery winnings Tina can win in the next $n$ days by playing the lottery infrequently.

Based on the above data, answer the given subquestions.

Let $L(i)$ be the cash payout of playing the lottery on day $i \in \{1, \ldots, n\}$. We need to keep track of most recent two plays (or equivalently, restrictions on future plays). Let $x(i, j)$ be maximum lottery winnings playing on suffix of days from $i$ to $n$, assuming play on day $i$ and next allowable play is on day $i + j$ for $i \in \{1, \ldots, n\}$ and $j \in \{1, \ldots, 6\}$. What is the final answer?

Tina stumbles upon a lottery chart dropped by a time traveler from the future, which lists winning lottery numbers and positive integer cash payouts for the next $n$ days. Tina wants to use this information to make money, but is worried if she plays winning numbers every day, lottery organizers will get suspicious. As such, she decides to play the lottery infrequently: at most twice in any seven day period.

In this problem, we will build up towards an $O(n)$-time algorithm to determine the maximum amount of lottery winnings Tina can win in the next $n$ days by playing the lottery infrequently.

Based on the above data, answer the given subquestions.

Tina stumbles upon a lottery chart dropped by a time traveler from the future, which lists winning lottery numbers and positive integer cash payouts for the next $n$ days. Tina wants to use this information to make money, but is worried if she plays winning numbers every day, lottery organizers will get suspicious. As such, she decides to play the lottery infrequently: at most twice in any seven day period.

In this problem, we will build up towards an $O(n)$-time algorithm to determine the maximum amount of lottery winnings Tina can win in the next $n$ days by playing the lottery infrequently.

Based on the above data, answer the given subquestions.

Tina stumbles upon a lottery chart dropped by a time traveler from the future, which lists winning lottery numbers and positive integer cash payouts for the next $n$ days. Tina wants to use this information to make money, but is worried if she plays winning numbers every day, lottery organizers will get suspicious. As such, she decides to play the lottery infrequently: at most twice in any seven day period.

In this problem, we will build up towards an $O(n)$-time algorithm to determine the maximum amount of lottery winnings Tina can win in the next $n$ days by playing the lottery infrequently.

Based on the above data, answer the given subquestions.

Let $G = (V, E)$ be a graph. A cut in $G$ is a partition of $V$ into two sets. Let $S \subseteq V$ be a subset of vertices. The cost of the cut $(S, V \backslash S)$, denoted by cost$(S)$, equals the number of edges between $S$ and $V \backslash S$, i.e., the size of the set $\{\{x, y\} \in E \mid x \in S, y \in V \backslash S\}$. The edges that have one endpoint in $S$ and the other in $V \backslash S$ are said to cross the cut.

The Maximum Cut Problem takes a graph $G = (V, E)$ as input and the objective is to find a cut with maximum cost.

Based on the above data, answer the given subquestions.

Let $G = (V, E)$ be a graph. A cut in $G$ is a partition of $V$ into two sets. Let $S \subseteq V$ be a subset of vertices. The cost of the cut $(S, V \backslash S)$, denoted by cost$(S)$, equals the number of edges between $S$ and $V \backslash S$, i.e., the size of the set $\{\{x, y\} \in E \mid x \in S, y \in V \backslash S\}$. The edges that have one endpoint in $S$ and the other in $V \backslash S$ are said to cross the cut.

The Maximum Cut Problem takes a graph $G = (V, E)$ as input and the objective is to find a cut with maximum cost.

Based on the above data, answer the given subquestions.

What is the maximum possible value of the cost of the maximum cut?

Let $G = (V, E)$ be a graph. A cut in $G$ is a partition of $V$ into two sets. Let $S \subseteq V$ be a subset of vertices. The cost of the cut $(S, V \backslash S)$, denoted by cost$(S)$, equals the number of edges between $S$ and $V \backslash S$, i.e., the size of the set $\{\{x, y\} \in E \mid x \in S, y \in V \backslash S\}$. The edges that have one endpoint in $S$ and the other in $V \backslash S$ are said to cross the cut.

The Maximum Cut Problem takes a graph $G = (V, E)$ as input and the objective is to find a cut with maximum cost.

Based on the above data, answer the given subquestions.

For $q \geqslant 1$, a $q$-approximation algorithm for maximum cut is an algorithm that is guaranteed to produce a cut whose cost is at least $\frac{1}{q}$ of the cost of the optimal cut of the input instance.

Suppose we can devise an algorithm that, given a graph $G$ on $m$ edges, is guaranteed to find a cut whose cost is at least $\frac{m}{2}$. Such an algorithm would be:

Let $G = (V, E)$ be a graph. A cut in $G$ is a partition of $V$ into two sets. Let $S \subseteq V$ be a subset of vertices. The cost of the cut $(S, V \backslash S)$, denoted by cost$(S)$, equals the number of edges between $S$ and $V \backslash S$, i.e., the size of the set $\{\{x, y\} \in E \mid x \in S, y \in V \backslash S\}$. The edges that have one endpoint in $S$ and the other in $V \backslash S$ are said to cross the cut.

The Maximum Cut Problem takes a graph $G = (V, E)$ as input and the objective is to find a cut with maximum cost.

Based on the above data, answer the given subquestions.

Consider the following trivial randomized algorithm that does not depend on the kind of the graph:

• Place each vertex $u$ in $S$ or $T$ independently and uniformly at random.

For this randomized method, it makes sense to talk about the expected value of the size of the cut, that we denote by E[ size of cut]. To analyze the expected size of the cut we will use the linearity of expectation:

$E[\alpha x + \beta x] = \alpha E[x] + \beta E[x]$

First, consider the following variable $X_e$ for a fixed edge $e$:

$X_e = \begin{cases} 1 & \text{if e is in the cut} \\ 0 & \text{otherwise} \end{cases}$

What is the expected value of $X_e$?

Let $G = (V, E)$ be a graph. A cut in $G$ is a partition of $V$ into two sets. Let $S \subseteq V$ be a subset of vertices. The cost of the cut $(S, V \backslash S)$, denoted by cost$(S)$, equals the number of edges between $S$ and $V \backslash S$, i.e., the size of the set $\{\{x, y\} \in E \mid x \in S, y \in V \backslash S\}$. The edges that have one endpoint in $S$ and the other in $V \backslash S$ are said to cross the cut.

The Maximum Cut Problem takes a graph $G = (V, E)$ as input and the objective is to find a cut with maximum cost.

Based on the above data, answer the given subquestions.

Recall the max-flow problem: for a directed graph $G(V, E)$ with non-negative capacities $c_e$ for every $e \in E$ and two special vertices $s$ (source, with no incoming edges) and $t$ (sink, with no outgoing edges), a flow in $G$ is an assignment $f : E \rightarrow \mathbb{R}_{\geq 0}$ such that $f_e \leq c_e$ for every edge and for every vertex $v \in V, \sum_{(u,v) \in E} f((u,v)) = \sum_{(v,u) \in E} f((v,u))$. The task is to find a maximum flow $f$ i.e., a flow $f$ such that $\sum_{(s,u) \in E} f((s,u))$ is maximized.

Given an instance $(G; s, t, c)$, we attempt here to design a LP whose optimal value is equal to the maximum flow in the graph $G$. There is a variable $x_{uv}$ for all $(u, v) \in E$. Note that for any pair of vertices that is not an edge, we do not introduce any variable corresponding to it.

$\begin{aligned} &\max \sum_u x_{ut} \\ &\forall e = (u,v) \in E, x_{uv} \leqslant c_e \\ &\forall v \notin \{s,t\}, \sum_u x_{uv} = \sum_w x_{vw} \\ &\forall e = (u,v) \in E, x_{uv} \geqslant 0 \end{aligned}$

Is the LP above a valid formulation for computing the maximum flow in $G$?

The EXACT-COVER-BY-3-SETS problem is defined as the following: given a finite set $X$ with $|X| = 3q$ and a collection $C$ of 3-element subsets of $X$, does $C$ contain an exact cover for $X$, that is, a subcollection $C' \subseteq C$ such that every element of $X$ occurs in exactly one member of $C'$?

The EXACT-COVER-BY-4-SETS problem is defined as the following: given a finite set $X$ with $|X| = 4q$ and a collection $C$ of 4-element subsets of $X$, does $C$ contain an exact cover for $X$, that is, a subcollection $C' \subseteq C$ such that every element of $X$ occurs in exactly one member of $C'$?

Given that EXACT-COVER-BY-3-SETS is NP-Complete, is EXACT-COVER-BY-4-SETS also NP-Complete?

Say problem X reduces to problem Y. Which of the following can we infer?