Advanced Algorithms End Term: 3 September 2023, Set QPE1-S2 (May 2023 term)

Recall the Dance Class problem:

Problem Definition

Dance Classes

Input: A collection of $n$ intervals given by their left and right endpoints $(s_1, f_1), \ldots, (s_n, f_n)$, where $s_i < f_i$ for all $1 \leqslant i \leqslant n$.

Question: What is the size of the largest collection of mutually pairwise non-overlapping intervals?

Consider the greedy approach to the problem where we repeat the following until there are no intervals left:

select the shortest interval, eliminating ties arbitrarily, add it to our solution and eliminate all overlapping intervals.

On which of the following instances will this algorithm produce a suboptimal answer?

Instance 1:

The number of classes is N = 4
The timings of the classes are given by:
1 - 2
3 - 4
5 - 6
7 - 8

Instance 2:

The number of classes is N = 4
The timings of the classes are given by:
4 - 5
3 - 6
2 - 7
1 - 8

Instance 3:

The number of classes is N = 4
The timings of the classes are given by:
1 - 7
8 - 15
6 - 9
16 - 20

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

True or false?
It is possible that Independent-Set is in P and the problem of checking a graph has a Hamiltonian Path is not in P.

Raj and Lata both designed an algorithm for the same minimization problem.

Raj proved that his algorithm $Alg1$ is a 2-approximation algorithm.
Lata proved that her algorithm $Alg2$ is a 4-approximation algorithm.

Is the following statement true or false?

There must be an input $I$ such that $Alg1(I) < Alg2(I)$.

Recall that to say that a problem has a $c$-approximation algorithm for some constant $c$ means that the output of the algorithm is always at most $c \cdot OPT(I)$ on all inputs $I$.

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, f(x_{uv}) \geq 0 \end{aligned}$

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

Recall the Dance Class problem:

Problem Definition

Dance Classes

Input: A collection of $n$ intervals given by their left and right endpoints $(s_1, f_1), \ldots, (s_n, f_n)$, where $s_i < f_i$ for all $1 \leqslant i \leqslant n$.

Question: What is the size of the largest collection of mutually pairwise non-overlapping intervals?

Consider the greedy approach to the problem where we repeat the following until there are no intervals left:

select the interval with ---------, eliminating ties arbitrarily; add it to our solution and eliminate all overlapping intervals.

Which of the following strategies guarantees an optimal result?

Recall the Stable Matching problem:

Stable Matching

Input: Two sets given by

• $M = \{m_1, \ldots, m_n\}$ (the men) and
• $W = \{w_1, \ldots, w_n\}$ (the women);

and two collections of rankings

• $\{\sigma_1, \ldots, \sigma_n\}$ (the ranking of the men over the women) and
• $\{\tau_1, \ldots, \tau_n\}$ (the ranking of the women over the men),

where for all $1 \leqslant i \leqslant n$, $\sigma_i$ is a strict ranking over $W$ and $\tau_i$ is a strict ranking over $M$.

Question: Find a permutation $\pi$ over $\{1, \ldots, n\}$ such that $\{m_i, w_{\pi(i)}\}_{i \in [n]}$ is a stable matching.

For completeness, we recall the definition of a stable matching.

Consider the matching $M := \{m_i, w_{\pi(i)}\}$ given by a permutation $\pi$ of $[n]$. A pair $(m_k, w_\ell)$ is said to be a blocking pair with respect to $M$ if:

• $\ell \neq \pi(k)$,
• $w_\ell$ is ranked higher than $w_{\pi(k)}$ in $\sigma_i$,
• $m_k$ is ranked higher than $m_q$ in $\tau_\ell$, where $\pi(q) = \ell$;

in other words, $m_k$ and $w_\ell$ are not matched by $M$, and they rank each other higher than their respective matched partners in $M$.

If $M$ is a matching for which there are no blocking pairs with respect to $M$, then $M$ is said to be a stable matching.

Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ).

P: W > X > Y > Z
Q: X > Y > Z > W
R: W > X > Z > Y
S: X > Y > W > Z

and

W: S > Q > R > P
X: P > S > Q > R
Y: R > P > Q > S
Z: R > P > S > Q

Consider the following matching: M = {(P, W), (Q, X), (R, Z), (S, Y)}.

Which of the following is a blocking pair in the matching above?

Based on the above data, answer the given subquestions.

Is the collection of outgoing 1/2-factors over the set A a matroid?

Based on the above data, answer the given subquestions.

Is the collection of incoming 1/2-factors over the set A a matroid?

Based on the above data, answer the given subquestions.

Is the collection of 1-factors over the set A a matroid?

Based on the above data, answer the given subquestions.

Can the collection of 1-factors be defined as the intersection of two matroids?

Based on the above data, answer the given subquestions.

The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2, 1), (1, 3), (1,2,1), (2, 1,3), (1,2, 1, 3).

As another example, if today the memory contains a single array {(7,7)},tomorrow it will contain the following arrays: {(7), (7), (7,7)}, and the day after tomorrow it will contain the following arrays: {(7), (7), (7), (7), (7,7)}, and so on.

You are given Bob's original array A and the number of days D. Let $f(A, D)$ be the sum of all elements of all arrays that will be in the memory of Bob's computer after D days. Our goal is to calculate $f(A, D)$. You may assume that the memory of Bob's computer is sufficiently large to accommodate all the arrays.

Based on the above data, answer the given subquestions.

The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2, 1), (1, 3), (1,2,1), (2, 1,3), (1,2, 1, 3).

As another example, if today the memory contains a single array {(7,7)},tomorrow it will contain the following arrays: {(7), (7), (7,7)}, and the day after tomorrow it will contain the following arrays: {(7), (7), (7), (7), (7,7)}, and so on.

You are given Bob's original array A and the number of days D. Let $f(A, D)$ be the sum of all elements of all arrays that will be in the memory of Bob's computer after D days. Our goal is to calculate $f(A, D)$. You may assume that the memory of Bob's computer is sufficiently large to accommodate all the arrays.

Based on the above data, answer the given subquestions.

The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2, 1), (1, 3), (1,2,1), (2, 1,3), (1,2, 1, 3).

As another example, if today the memory contains a single array {(7,7)},tomorrow it will contain the following arrays: {(7), (7), (7,7)}, and the day after tomorrow it will contain the following arrays: {(7), (7), (7), (7), (7,7)}, and so on.

You are given Bob's original array A and the number of days D. Let $f(A, D)$ be the sum of all elements of all arrays that will be in the memory of Bob's computer after D days. Our goal is to calculate $f(A, D)$. You may assume that the memory of Bob's computer is sufficiently large to accommodate all the arrays.

Based on the above data, answer the given subquestions.

The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2, 1), (1, 3), (1,2,1), (2, 1,3), (1,2, 1, 3).

As another example, if today the memory contains a single array {(7,7)},tomorrow it will contain the following arrays: {(7), (7), (7,7)}, and the day after tomorrow it will contain the following arrays: {(7), (7), (7), (7), (7,7)}, and so on.

You are given Bob's original array A and the number of days D. Let $f(A, D)$ be the sum of all elements of all arrays that will be in the memory of Bob's computer after D days. Our goal is to calculate $f(A, D)$. You may assume that the memory of Bob's computer is sufficiently large to accommodate all the arrays.

Based on the above data, answer the given subquestions.

If A has four elements, how many arrays of length one are there after two steps?

The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2, 1), (1, 3), (1,2,1), (2, 1,3), (1,2, 1, 3).

As another example, if today the memory contains a single array {(7,7)},tomorrow it will contain the following arrays: {(7), (7), (7,7)}, and the day after tomorrow it will contain the following arrays: {(7), (7), (7), (7), (7,7)}, and so on.

You are given Bob's original array A and the number of days D. Let $f(A, D)$ be the sum of all elements of all arrays that will be in the memory of Bob's computer after D days. Our goal is to calculate $f(A, D)$. You may assume that the memory of Bob's computer is sufficiently large to accommodate all the arrays.

Based on the above data, answer the given subquestions.

Suppose we store, for every pair of indices $1 \leq i \leq j \leq N$, the number of times the subarray $A[i:j]$ (i, j inclusive) appears in the memory of Bob's computer on a particular day. Specifically, let $T[i, j, d]$ denote the number of occurrences of $A[i:j]$ in the set of arrays generated after $d$ days. Then:

Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity across a particular edge.

The value of the maximum flow in the given network is: ______________

You are supposed to start at the top of a number triangle and chose your passage all the way down by selecting between the numbers below you to the immediate left or right. Your goal is to maximize the sum of the elements lying in your path.
For example, in the triangle below, the red path maximizes the sum.

Consider the following orientation problem.

We are given an undirected graph $G = (V, E)$ and integer values $p(v)$ for every vertex $v \in V$. We would like to know if we can orient the edges of $G$ such that the directed graph we obtain has at most $p(v)$ arcs incoming to $v$ (the 'in-degree requirements').

In other words, for each edge $\{u, v\}$, we have to decide whether to orient it as $(u, v)$ or as $(v, u)$, and we would like at most $p(v)$ arcs to be oriented towards $v$.

This problem is:

Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity across a particular edge.

Which of the following edges form a valid min-cut in the given network?

Based on the above data, answer the given subquestions.

Consider the partially carefully properly 5-colored graph below. What color should we give the vertex in the center to extend this to a complete careful proper 5-coloring?

Based on the above data, answer the given subquestions.

In the Uncapacitated Facility Location (UCFL) problem, we are given $(\mathcal{F} \uplus \mathcal{D}, d)$ as well auxiliary information which specifies the cost $f_i$ of opening a facility at location $i \in \mathcal{F}$. The goal is to open a subset of facilities in $\mathcal{F}$ to minimize the sum of the cost of the opened facilities and the total distance traveled by the clients to their nearest open facility.

In other words we want to solve

$\min_{\mathcal{F}' \subseteq \mathcal{F}} \left( \sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{D}} d\left(j, \mathcal{F}'\right) \right).$

Consider the following LP formulation for the problem. We use a variable $y_i$ for $i \in \mathcal{F}$ to indicate whether $i$ is opened or not. We use a variable $x_{i,j}$ to indicate whether $j$ is assigned to $i$. One set of constraints are natural here: each client has to be assigned/connected to a facility. The other constraint requires that $j$ is assigned to $i$ only if $i$ is open.

Consider the LP below:

$\begin{aligned} &\min \sum_{i \in \mathcal{F}} f_i y_i + \sum_{j \in \mathcal{D}} \sum_{i \in \mathcal{F}} d(i,j) x_{i,j} \\ &\qquad \sum_i x_{i,j} = Q \quad \forall j \in \mathcal{D} \\ &\qquad x_{i,j} \leqslant y_i \quad i \in \mathcal{F}, j \in \mathcal{D} \\ &\qquad x, y \geqslant 0 \end{aligned}$

What is the correct value of Q?

Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asterisks (*) :

For the following parts, choose the tightest big-Oh bound that applies.

Based on the above data, answer the given subquestions.

What is the expected number of :)'s that randomizedSmiles prints out?

Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asterisks (*) :

For the following parts, choose the tightest big-Oh bound that applies.

Based on the above data, answer the given subquestions.

What is the maximum number of :)'s that randomizedSmiles can print out, if you got to choose how p is selected?

Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asterisks (*) :

For the following parts, choose the tightest big-Oh bound that applies.

Based on the above data, answer the given subquestions.

What is the expected number of 's that randomizedSmiles prints out?

Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asterisks (*) :

For the following parts, choose the tightest big-Oh bound that applies.

Based on the above data, answer the given subquestions.

What is the maximum number of 's that randomizedSmiles can print out, if you got to choose how p is selected?

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.

Recall the Traveling Salesman Problem:

Definition

Traveling Salesman Problem

Input: A set of distinct cities $\{c_1, c_2, \ldots, c_n\}$ and for each pair $c_i \neq c_j$ the distance between $c_i$ and $c_j$, denoted by $d(c_i, c_j)$, and a budget $k$.

Question: Determine if there is a permutation $\pi$ of $\{1, 2, \ldots, n\}$, such that the following sum:

$\sum_{i=1}^{n-1} d\left(c_{\pi(i)}, c_{\pi(i+1)}\right) + d\left(c_{\pi(n)}, c_{\pi(1)}\right)$

is at most $k$.

The dynamic programming algorithm for TSP computes for every pair $(S, c_i)$, where $S$ is a nonempty subset of $\{c_2, c_3, \ldots, c_n\}$ and $c_i \in S$, the value $OPT[S, c_i]$ which is the minimum length of a tour which starts in $c_1$, visits all cities from $S$ and ends in $c_i$. We compute the values $OPT[S, c_i]$ in order of increasing cardinality of $S$. The computation of $OPT[S, c_i]$ in the case $S$ contains only one city is trivial, because in this case, $OPT[S, c_i] = d(c_1, c_i)$. For the case $|S| > 1$, observe that if in some optimal tour in $S$ terminating in $c_i$, the city $c_j$ immediately precedes $c_i$, then

$OPT[S, c_i] = OPT[S \setminus \{c_i\}, c_j] + d(c_j, c_i).$

This leads us to expressing the value of $OPT[S, c_i]$ in terms of subsets of $S$ as follows.

$OPT[S, c_i] = \min\{OPT[S \setminus \{c_i\}, c_j] + \star : c_j \in S \setminus \{c_i\}\}.$

Note that the minimum is taken over $c_j \in S \setminus \{c_i\}$. What is the missing term?