Advanced Algorithms Quiz 2: 1 December 2024 (September 2024 term)

Based on the above data answer the given subquestions.

Based on the above data answer the given subquestions.

Consider the following reduction from 3-PARTITION to 2-PARTITION: let $\{a_1, \ldots, a_{3n}\}$ be the instance of 3-PARTITION where $\sum_{i=1}^{3n} a_i = nT$. Now consider the instance of 2-PARTITION made of the numbers:

$\{a_1, T - a_1, a_2, T - a_2, \ldots, a_n, T - a_n\},$

i.e, the reduced instance consists of the first $n$ numbers of the original problem, and $n$ new numbers formed by taking the difference between each of the input numbers and the common sum $T$. This reduction:

Based on the above data answer the given subquestions.

Consider the following reduction from 3-PARTITION to 2-PARTITION: let $\{a_1, \ldots, a_{3n}\}$ be the instance of 3-PARTITION where $\sum_{i-1}^{3n} a_i = nT$. Now consider the instance of 2-PARTITION made of the numbers:

$\{a_1, a_2, \ldots, a_{2n}\},$

i.e, the reduced instance simply consists of the first $2n$ numbers of the 3-PARTITION instance. This reduction:

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.

Based on the above data answer the given subquestions.

Based on the above data answer the given subquestions.

Observe that for a given $\pi$, the length of the corresponding superstring $s(\pi)$, which is obtained by writing the input strings in the order $\left(s_{\pi(1)}, \ldots, s_{\pi(n)}\right)$ and merging adjacent strings, is given by:

$|s(\pi)| = \sum_{i=1}^{n} |s_i| - \sum_{i=1}^{n-1} \left|\operatorname{ov}\left(s_{\pi(i)}, s_{\pi(i+1)}\right)\right|.$

The compression of $\pi$ is the sum of the overlaps of adjacent strings in the permutation $\pi$. Finding a shortest superstring is equivalent to:

Based on the above data answer the given subquestions.

We define an overlap graph $OG(\mathcal{S})$ associated with $\mathcal{S}$ as follows: $OG(\mathcal{S})$ is a complete directed graph $(V, E)$ (that is, for every $s, t \in V$ there are edges $(s, t)$ and $(t, s)$), where $V = \mathcal{S}$, and the weight of an edge $(s, t)$ is $|\operatorname{ov}(s, t)|$.

Let us say that an edge $(u, v)$ dominates another edge $(u', v')$, if they share head or tail (that is, $u = u'$ or $v = v'$) and $|\operatorname{ov}(u, v)| \geqslant |\operatorname{ov}(u', v')|$.

In terms of the overlap graph, the greedy algorithm goes through a list of all edges in $OG(\mathcal{S})$ in the nonincreasing order of their overlap and includes some of them in a solution. Specifically, the greedy algorithm does not include another edge if and only if

R1. it is dominated by an already chosen edge,

R2. it is not dominated but it would form a cycle.

What is the structure of the set of edges returned by the greedy algorithm?

Based on the above data answer the given subquestions.