Advanced Algorithms Quiz 1: 13 July 2025 (May 2025 term)

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.

Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?
For each statement given in the subquestions, determine if it is true or false.

There is a polynomial-time reduction from BoxDepth to MaxClique.

Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?
For each statement given in the subquestions, determine if it is true or false.

There is a polynomial-time algorithm for BoxDepth.

Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?
For each statement given in the subquestions, determine if it is true or false.

Only one of the statements in the previous question can be true assuming P ≠ NP.

Suppose your friend comes up with an algorithm to solve Partition in time O(nM), where n is the size of the input set and M is the sum of the absolute values of its elements. Which of the following statements is correct?

The problem AllOrNothing3Sat asks, given a 3CNF boolean formula, whether there is an assignment to the variables such that each clause either has three True literals or has three False literals.
Consider the following statements:
(1) There is a polynomial-time algorithm to solve AllOrNothing3Sat.
(2) There is a polynomial-time reduction from 3SAT to AllOrNothing3Sat.
Assuming P ≠ NP, which of the following is true?

Which of the following statements is true about a flow network?

Given a flow network (G, s, t, c) and a flow f, how will you determine if f is maximum flow?

In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of three columns and four rows, they are obtained by placing a point in each ofthe four possible positions (accounting for symmetries), and then a circle in each of the other possible positions. Some example cards are shown below.

Based on the above data, answer the given subquestions.

SWISH-SPECIAL is in P.

In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of three columns and four rows, they are obtained by placing a point in each ofthe four possible positions (accounting for symmetries), and then a circle in each of the other possible positions. Some example cards are shown below.

Based on the above data, answer the given subquestions.

SWISH-SPECIAL is in NP.

In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of three columns and four rows, they are obtained by placing a point in each ofthe four possible positions (accounting for symmetries), and then a circle in each of the other possible positions. Some example cards are shown below.

Based on the above data, answer the given subquestions.

SWISH-SPECIAL is NP-hard.

In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of three columns and four rows, they are obtained by placing a point in each ofthe four possible positions (accounting for symmetries), and then a circle in each of the other possible positions. Some example cards are shown below.

Based on the above data, answer the given subquestions.

SWISH-SPECIAL is NP-complete.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Suppose $n = 2, N = 100$ and the randomly assigned weights are:

$w(1) = 25, w(2) = 25$

Consider all non-empty families $\mathcal{F}$ over non-empty subsets of $\{1, 2\}$. There are seven such families. How many of them do not have a unique minimum-weight subset?

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

We introduce some notation:

• Let $\mathcal{P}_i \subseteq \mathcal{F}$ denote all those sets in $\mathcal{F}$ that contain $i$, and
• let $\mathcal{Q}_i \subseteq \mathcal{F}$ denote all those sets in $\mathcal{F}$ that do not contain $i$.

Notice that $\mathcal{Q}_i = \mathcal{F} \setminus \mathcal{P}_i$. For example, if $\mathcal{F} = \{\{1\}, \{1, 2\}, \{2, 3\}\}$, then:

• $\mathcal{P}_1 = \{\{1\}, \{1, 2\}\}$ and $\mathcal{Q}_1 = \{\{2, 3\}\}$, and
• $\mathcal{P}_2 = \{\{1, 2\}, \{2, 3\}\}$ and $\mathcal{Q}_2 = \{\{1\}\}$, and
• $\mathcal{P}_3 = \{\{2, 3\}\}$ and $\mathcal{Q}_3 = \{\{1\}, \{1, 2\}\}$.

Let $\mathcal{E}_i$ be the event:

$\min\{w(S) : \mathcal{P}_i\} = \min\{w(S) : S \in \mathcal{Q}_i\}.$

We can conclude that the good event occurs if:

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Further, if the good event occurs, then:

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

Consider the problem of finding perfect matchings in a simple, undirected graph. Recall that the Tutte matrix of a graph $G$, denoted $Z_G$, is given by:

$Z_G[i, j] = \begin{cases} z_{ij} & \text{if } (i, j) \text{ is an edge and } i < j \\ -z_{ji} & \text{if } (i, j) \text{ is an edge and } j > i \\ 0 & \text{if } (i, j) \text{ is not an edge} \end{cases}$

Suppose each edge is assigned a random weight in $\{1, \ldots, 2m\}$, and $\mathcal{F}$ is the set of perfect matchings. Further, let us replace each indeterminate $z_{ij}$ in the Tutte matrix of the graph is replaced with $2^{w_{ij}}$ where $w_{ij}$ is the randomly assinged weights of the edge $(i, j)$ from above.

If $G$ has no perfect matching, what is the determinant of $Z$ with the variables substituted for these weights?

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

We continue the notation from the previous question. Suppose the randomly assigned weights lead to the good event, that is, there is an unique perfect matching in G with minimum weight, and say this minimum weight is r. What can you say about the determinant of Z in this case?