Advanced Algorithms Quiz 2: 6 August 2023 (May 2023 term)

For the following sets of timings of dance classes, figure out what is the largest number of classes that you can attend in a conflict-free fashion:

The number of classes is N = 9. The timings of the classes are given by:

1. [1 - 5]
2. [6 - 10]
3. [11- 15]
4. [16 - 20]
5. [2 - 8]
6. [3 - 8]
7. [2 - 7]
8. [9 - 12]
9. [13 - 17]

Consider 4 sets as follows: $W = \{w_1, w_2, w_3\}$, $X = \{x_1, x_2\}$, $Y = \{y_1, y_2, y_3\}$ and $Z = \{z_1, z_2\}$.

Given capacity constraints are as follows:

$c(w_2) = c(y_1) = c(y_3) = 1,$

$c(w_1) = c(w_3) = c(x_2) = c(y_2) = c(z_1) = 2,$

$c(x_1) = c(z_2) = 3$

$c(w_i, x_i) = 1, \text{ for all } w_i \in W \text{ and all } x_i \in X,$

$c(y_i, z_i) = 1, \text{ for all } y_i \in Y \text{ and all } z_i \in Z$

$c(x_1, y_1) = 1, c(x_1, y_2) = 2, c(x_1, y_3) = 1$

$c(x_2, y_1) = 0, c(x_2, y_2) = 2, c(x_2, y_3) = 1.$

Identify the size of a largest collection of 4-tuples from the sets $W, X, Y$ and $Z$ satisfying the given constraints

Let $G$ be a simple, undirected, unweighted graph.

We use $V(G)$ to denote the vertex set of $G$ and $E(G)$ to denote the edge set of $G$.

Recall that if we have an empty graph (i.e, a graph where $V(G) = E(G) = \emptyset$), then by convention it (vacuously) satisfies the properties suggested in the given subquestions

Consider the set system $(U, \mathcal{F})$ defined as follows.

• The universe $U$ is $V(G)$.
• A subset of vertices $S \subseteq V(G)$ belongs to $\mathcal{F}$ if the subgraph induced by $S$ has maximum degree three.

Which of the following properties is/are NOT satisfied by $\mathcal{F}$?

Let $G$ be a simple, undirected, unweighted graph.

We use $V(G)$ to denote the vertex set of $G$ and $E(G)$ to denote the edge set of $G$.

Recall that if we have an empty graph (i.e, a graph where $V(G) = E(G) = \emptyset$), then by convention it (vacuously) satisfies the properties suggested in the given subquestions

Consider the set system $(U, \mathcal{F})$ defined as follows.

• The universe $U$ is $V(G)$.
• A subset of vertices $S \subseteq V(G)$ belongs to $\mathcal{F}$ if the subgraph induced by $S$ has minimum degree three.

Which of the following properties is/are NOT satisfied by $\mathcal{F}$?

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to Stone $i+1$ or Stone $i+2$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Towards solving this problem, note that the frog, can jump to only (i + 1) or (i + 2) from a position i. We will now try to define a recurrence that leads us to the solution.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. For our base cases, note that we have the following:

• dp[0] = 0 and
• dp[1] = abs(H[1] − H[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Based on the above data, answer the given subquestions.

Which of the following is a valid recurrence for dp[i]?

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to Stone $i+1$ or Stone $i+2$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Towards solving this problem, note that the frog, can jump to only (i + 1) or (i + 2) from a position i. We will now try to define a recurrence that leads us to the solution.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. For our base cases, note that we have the following:

• dp[0] = 0 and
• dp[1] = abs(H[1] − H[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Based on the above data, answer the given subquestions.

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$. We are also given an additional parameter $K \leqslant N-1$ which denotes the maximum jump length.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to one of the following: Stone $i+1, i+2, \ldots, i+K$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Based on the above data, answer the given subquestions.

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$. We are also given an additional parameter $K \leqslant N-1$ which denotes the maximum jump length.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to one of the following: Stone $i+1, i+2, \ldots, i+K$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Based on the above data, answer the given subquestions.

Consider the following program that attempts to solve this problem.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. We set dp[0] = 0 and dp[i] to infinity for all $1 \leqslant i \leqslant N-1$.

We then propose to populate dp according to the code below.

Which of the following statements is true about the code snippet above? Select all that apply.

Which of the following statements is true?
Statement 1: For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that’s possible in the graph.
Statement 2: Suppose the maximum (s, t)-flow of some graph has value f. Now we increase the capacity of every edge by 1. Then the maximum (s, t)-flow in this modified graph will have value at most f + 1.

Consider the following definitions:

• A vertex cover is a subset $S$ of $V(G)$ such that for all $(u,v) \in E(G)$, $S \cap \{u,v\} \neq \emptyset$.
• An independent set is a subset $S$ of $V(G)$ such that for all $(u,v) \in S$, $\{u,v\} \notin E(G)$.
• A maximum matching in $G$ is a largest collection of edges $F \subseteq E(G)$ such that no two edges in $F$ have a common endpoint.
• A feedback vertex set is a subset $S$ of $V(G)$ such that $G \setminus S$ is acyclic.
• An odd cycle transversal is a subset $S$ of $V(G)$ such that $G \setminus S$ is bipartite.

Which of the following is not a valid lower bound for the size of a minimum vertex cover of a graph $G$?

Consider a different rounding strategy for the LP relaxation of the vertex cover problem. Instead of rounding up every vertex whose value is at least $0.5$ after running the LP, we do the following:

We look at every edge, and then we round up the variable of the endpoint with the highest value, where in case of ties we take the endpoint with the highest index.

In other words, if the vertex set is $V = \{v_1, \ldots, v_n\}$ and we denote the associated variable of $v_i$ by $x_i$ then the cover $C$ is computed as follows:

$C := \{v_i \in V : \text{there is an edge } (v_i, v_j) \text{ such that } (x_i > x_j) \text{ or } (x_i = x_j \text{ and } i > j)\}$

Which statement is true?