Advanced Algorithms End Term: 1 September 2024, Set QDB3 (May 2024 term)

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

Can the disk with dimensions [2,1,2] be placed above [3,2,3]?

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

Can the disk with dimensions [2,2,2] be placed above [3,2,3]?

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

Suppose the input consists of the following triplets: [[3, 8, 8], [2, 1, 9], [4, 1, 1], [2, 3, 6]]. What’s the answer?

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

Our approach will be to building a DP table of the same length as the array of disks. Let $d_i$ denote the $i^{th}$ disk in the input array. The value of $\text{DP}[i]$ will be the height of the tallest tower that can be created with $d_i$ the bottom. We initialize the value of $\text{DP}[i]$ the height of $d_i$.

Consider the following approach. We process the DP array in increasing order of indices (i.e, $i = 1$ to $i = N$). We look at all disks $d_j$ where $j < i$ and $d_j$ can be placed on top of $d_i$. If $d_j$ can be placed on top of $d_i$, then $\text{DP}[i]$ is updated to be the maximum of $\text{DP}[i]$ and $\text{DP}[j] + H$, where $H$ is the height of the disk $d_i$.

What can you say about this approach?

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

With the same notation as in the previous question, consider the following alternate approach.We process the DP array in increasing order of indices (i.e, $i = 1$ to $i = N$). We look at all disks $d_j$ such that $d_j$ can be placed on top of $d_i$. If $d_j$ can be placed on top of $d_i$, then $\text{DP}[i]$ is updated to be the maximum of $\text{DP}[i]$ and $\text{DP}[j] + H$, where $H$ is the height of the disk $d_i$.

Note that the DP array is initialized as before, that is, $\text{DP}[i]$ is initialized to the height of $d_i$. What can you say about this approach?

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

With the same notation as in the previous questions, consider the following alternate approach. We first organize the disks in non-decreasing order of heights, that is, $d_1$ is a disk that has the smallest height, while $d_N$ is a disk that has the largest height.

We process the DP array in increasing order of indices (i.e, $i = 1$ to $i = N$). We look at all disks $d_j$ where $j < i$ such that $d_j$ can be placed on top of $d_i$.

If $d_j$ can be placed on top of $d_i$, then $\text{DP}[i]$ is updated to be the maximum of $\text{DP}[i]$ and $\text{DP}[j] + H$, where $H$ is the height of the disk $d_i$.

What can you say about this approach?

We are given a non-empty list of N ordered triplets where each triplet holds three integers and represents a cuboid-shaped disk. These integers denote each disk’s width, depth, and height, respectively. Your goal is to stack up the disks and to maximize the total height of the stack. A disk must have a strictly smaller width, depth, and height than any other disk below it.
Our goal is to design an algorithm that returns the total height of the optimal stack, starting with the top disk and ending with the bottom disk. Note that you can’t rotate disks. You can assume that there will only be one stack with the greatest total height. We also use 1-based indexing in the subquestions.
Based on the above data, answer the given subquestions.

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

If we have 1 die with 6 sides, how many ways can we achieve a target sum of 4?

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

If we have 3 dice with 17 sides each, how many ways can we achieve a target sum of 7?

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

Suppose the input consists of 3 dice, each with 4 sides, and the target sum is 9. What’s the answer?

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

In which of the following scenarios will the answer be zero?

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

If we have one die with six sides, what are the achievable targets?

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

What is the value of DP[0, 0]?

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

We are given a set of $N$ dice, each with $S$ sides, and a target integer $T$, which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.

All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to $S$.

Identical total dice rolls obtained from different individual dice rolls (for example, $[2, 3]$ vs. $[3, 2]$) count as different dice-roll permutations.

If there's no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.

Based on the above data, answer the given subquestions.

What is the complexity of this algorithm?

In this question, we use $[3]$ to denote $\{1, 2, 3\}$.

Let $G$ be a simple undirected finite graph. A function $f : V(G) \to [3]$ is called a proper 3-coloring of $G$ if no two adjacent vertices in $G$ have the same image under $f$. You can imagine $f$ coloring the vertices of the graph with colors 1, 2, and 3 (all vertices that have image 1 under $f$ are 'colored' 1, and so on); and such a coloring is proper if and only if there are no edges between vertices that have the same color.

In this question, we will explore ideas involving building up a DP-based solution for this problem for graphs of bounded treewidth using nice tree decompositions.

Let $\mathcal{T}(T, \{X_t\}_{t \in V(T)})$ be a rooted nice tree decomposition of $G$. For every node $t \in V(T)$, let $T_t$ denote the subtree of $T$ rooted at $t$.

For every node $x \in V(T)$ and every function $\chi : X_x \to [3]$, let $f(x, \chi)$ be defined as follows:

$f(x, \chi) := \text{TRUE}$ if there exists a function $\sigma : \bigcup_{\beta \in V(T_x)} X_\beta \to [3]$ such that

• $\forall u \in X_x : \ \big(\chi(u) = \sigma(u)\big)$
• No two adjacent vertices in $G\left[\bigcup_{\beta \in V(T_x)} X_\beta\right]$ have the same image under $\sigma$.

Otherwise, $f(x, \chi) := \text{FALSE}$.

The intuition for these definitions is the following. Fix a node $x \in V(T)$. Then $\chi$ describes a 3-coloring of the vertices in the bag $X_x$, which is not necessarily a proper 3-coloring. The function $f(x, \chi)$ describes if $\chi$ can be extended to a proper 3-coloring of the vertices in the subtree of $T$ rooted at $x$.

Now, let $v \in V(G)$. Let $a, b \in V(T)$ such that $v$ is introduced at $a$, and $b$ is the child of $a$.

Let $\theta : X_a \to [3]$ be a function such that

$\forall y \in X_a \cap N_G(v) : \quad \big(\theta(y) \neq \theta(v)\big)$

In other words, $\theta$ is a three-coloring of $X_a$ which ensures that the color of $v$ is different from the color of any of its neighbors in $X_a$.

Let $\theta' : X_b \to [3]$ be defined as follows:

$\forall y \in X_b : \quad \theta'(y) := \theta(y)$

Note that $X_b = X_a \cup \{v\}$ and thus $\theta'$ is simply the projection of $\theta$ on $X_b$.

Let $w \in V(G)$. Let $c, d \in V(T)$ such that $w$ is forgotten at $c$, and $d$ is the child of $c$.

In other words, $X_c = X_d \setminus \{w\}$.

Let $\psi : X_c \to [3]$ be a function. For every $i \in [3]$, let $\psi'_i : X_d \to [3]$ be defined as follows:

$\begin{aligned} \forall y \in X_d \setminus \{w\} : \quad & \psi'_i(y) := \psi(y) \\ & \psi'_i(w) := i \end{aligned}$

To explain this, assume that $\psi$ is a given 3-coloring of the parent node $X_c$. Now we define three colorings that extend $\psi$ in the child node $X_d$. For a fixed color $i \in [3]$, we are coloring every vertex in $X_d$ other than $w$ in the same way that it was colored in $X_c$ under $\psi$, and we are coloring $w$ with color $i$.

Let $e, g, h \in V(T)$ such that $e$ is a join node, and $g$ and $h$ are the children of $e$, and let $\lambda : X_e \to [3]$.

Based on the above data, answer the given subquestions.

In this question, we use $[3]$ to denote $\{1, 2, 3\}$.

Let $G$ be a simple undirected finite graph. A function $f : V(G) \to [3]$ is called a proper 3-coloring of $G$ if no two adjacent vertices in $G$ have the same image under $f$. You can imagine $f$ coloring the vertices of the graph with colors 1, 2, and 3 (all vertices that have image 1 under $f$ are 'colored' 1, and so on); and such a coloring is proper if and only if there are no edges between vertices that have the same color.

In this question, we will explore ideas involving building up a DP-based solution for this problem for graphs of bounded treewidth using nice tree decompositions.

Let $\mathcal{T}(T, \{X_t\}_{t \in V(T)})$ be a rooted nice tree decomposition of $G$. For every node $t \in V(T)$, let $T_t$ denote the subtree of $T$ rooted at $t$.

For every node $x \in V(T)$ and every function $\chi : X_x \to [3]$, let $f(x, \chi)$ be defined as follows:

$f(x, \chi) := \text{TRUE}$ if there exists a function $\sigma : \bigcup_{\beta \in V(T_x)} X_\beta \to [3]$ such that

• $\forall u \in X_x : \ \big(\chi(u) = \sigma(u)\big)$
• No two adjacent vertices in $G\left[\bigcup_{\beta \in V(T_x)} X_\beta\right]$ have the same image under $\sigma$.

Otherwise, $f(x, \chi) := \text{FALSE}$.

The intuition for these definitions is the following. Fix a node $x \in V(T)$. Then $\chi$ describes a 3-coloring of the vertices in the bag $X_x$, which is not necessarily a proper 3-coloring. The function $f(x, \chi)$ describes if $\chi$ can be extended to a proper 3-coloring of the vertices in the subtree of $T$ rooted at $x$.

Now, let $v \in V(G)$. Let $a, b \in V(T)$ such that $v$ is introduced at $a$, and $b$ is the child of $a$.

Let $\theta : X_a \to [3]$ be a function such that

$\forall y \in X_a \cap N_G(v) : \quad \big(\theta(y) \neq \theta(v)\big)$

In other words, $\theta$ is a three-coloring of $X_a$ which ensures that the color of $v$ is different from the color of any of its neighbors in $X_a$.

Let $\theta' : X_b \to [3]$ be defined as follows:

$\forall y \in X_b : \quad \theta'(y) := \theta(y)$

Note that $X_b = X_a \cup \{v\}$ and thus $\theta'$ is simply the projection of $\theta$ on $X_b$.

Let $w \in V(G)$. Let $c, d \in V(T)$ such that $w$ is forgotten at $c$, and $d$ is the child of $c$.

In other words, $X_c = X_d \setminus \{w\}$.

Let $\psi : X_c \to [3]$ be a function. For every $i \in [3]$, let $\psi'_i : X_d \to [3]$ be defined as follows:

$\begin{aligned} \forall y \in X_d \setminus \{w\} : \quad & \psi'_i(y) := \psi(y) \\ & \psi'_i(w) := i \end{aligned}$

To explain this, assume that $\psi$ is a given 3-coloring of the parent node $X_c$. Now we define three colorings that extend $\psi$ in the child node $X_d$. For a fixed color $i \in [3]$, we are coloring every vertex in $X_d$ other than $w$ in the same way that it was colored in $X_c$ under $\psi$, and we are coloring $w$ with color $i$.

Let $e, g, h \in V(T)$ such that $e$ is a join node, and $g$ and $h$ are the children of $e$, and let $\lambda : X_e \to [3]$.

Based on the above data, answer the given subquestions.

In this question, we use $[3]$ to denote $\{1, 2, 3\}$.

Let $G$ be a simple undirected finite graph. A function $f : V(G) \to [3]$ is called a proper 3-coloring of $G$ if no two adjacent vertices in $G$ have the same image under $f$. You can imagine $f$ coloring the vertices of the graph with colors 1, 2, and 3 (all vertices that have image 1 under $f$ are 'colored' 1, and so on); and such a coloring is proper if and only if there are no edges between vertices that have the same color.

In this question, we will explore ideas involving building up a DP-based solution for this problem for graphs of bounded treewidth using nice tree decompositions.

Let $\mathcal{T}(T, \{X_t\}_{t \in V(T)})$ be a rooted nice tree decomposition of $G$. For every node $t \in V(T)$, let $T_t$ denote the subtree of $T$ rooted at $t$.

For every node $x \in V(T)$ and every function $\chi : X_x \to [3]$, let $f(x, \chi)$ be defined as follows:

$f(x, \chi) := \text{TRUE}$ if there exists a function $\sigma : \bigcup_{\beta \in V(T_x)} X_\beta \to [3]$ such that

• $\forall u \in X_x : \ \big(\chi(u) = \sigma(u)\big)$
• No two adjacent vertices in $G\left[\bigcup_{\beta \in V(T_x)} X_\beta\right]$ have the same image under $\sigma$.

Otherwise, $f(x, \chi) := \text{FALSE}$.

The intuition for these definitions is the following. Fix a node $x \in V(T)$. Then $\chi$ describes a 3-coloring of the vertices in the bag $X_x$, which is not necessarily a proper 3-coloring. The function $f(x, \chi)$ describes if $\chi$ can be extended to a proper 3-coloring of the vertices in the subtree of $T$ rooted at $x$.

Now, let $v \in V(G)$. Let $a, b \in V(T)$ such that $v$ is introduced at $a$, and $b$ is the child of $a$.

Let $\theta : X_a \to [3]$ be a function such that

$\forall y \in X_a \cap N_G(v) : \quad \big(\theta(y) \neq \theta(v)\big)$

In other words, $\theta$ is a three-coloring of $X_a$ which ensures that the color of $v$ is different from the color of any of its neighbors in $X_a$.

Let $\theta' : X_b \to [3]$ be defined as follows:

$\forall y \in X_b : \quad \theta'(y) := \theta(y)$

Note that $X_b = X_a \cup \{v\}$ and thus $\theta'$ is simply the projection of $\theta$ on $X_b$.

Let $w \in V(G)$. Let $c, d \in V(T)$ such that $w$ is forgotten at $c$, and $d$ is the child of $c$.

In other words, $X_c = X_d \setminus \{w\}$.

Let $\psi : X_c \to [3]$ be a function. For every $i \in [3]$, let $\psi'_i : X_d \to [3]$ be defined as follows:

$\begin{aligned} \forall y \in X_d \setminus \{w\} : \quad & \psi'_i(y) := \psi(y) \\ & \psi'_i(w) := i \end{aligned}$

To explain this, assume that $\psi$ is a given 3-coloring of the parent node $X_c$. Now we define three colorings that extend $\psi$ in the child node $X_d$. For a fixed color $i \in [3]$, we are coloring every vertex in $X_d$ other than $w$ in the same way that it was colored in $X_c$ under $\psi$, and we are coloring $w$ with color $i$.

Let $e, g, h \in V(T)$ such that $e$ is a join node, and $g$ and $h$ are the children of $e$, and let $\lambda : X_e \to [3]$.

Based on the above data, answer the given subquestions.

In this question, we use $[3]$ to denote $\{1, 2, 3\}$.

Let $G$ be a simple undirected finite graph. A function $f : V(G) \to [3]$ is called a proper 3-coloring of $G$ if no two adjacent vertices in $G$ have the same image under $f$. You can imagine $f$ coloring the vertices of the graph with colors 1, 2, and 3 (all vertices that have image 1 under $f$ are 'colored' 1, and so on); and such a coloring is proper if and only if there are no edges between vertices that have the same color.

In this question, we will explore ideas involving building up a DP-based solution for this problem for graphs of bounded treewidth using nice tree decompositions.

Let $\mathcal{T}(T, \{X_t\}_{t \in V(T)})$ be a rooted nice tree decomposition of $G$. For every node $t \in V(T)$, let $T_t$ denote the subtree of $T$ rooted at $t$.

For every node $x \in V(T)$ and every function $\chi : X_x \to [3]$, let $f(x, \chi)$ be defined as follows:

$f(x, \chi) := \text{TRUE}$ if there exists a function $\sigma : \bigcup_{\beta \in V(T_x)} X_\beta \to [3]$ such that

• $\forall u \in X_x : \ \big(\chi(u) = \sigma(u)\big)$
• No two adjacent vertices in $G\left[\bigcup_{\beta \in V(T_x)} X_\beta\right]$ have the same image under $\sigma$.

Otherwise, $f(x, \chi) := \text{FALSE}$.

The intuition for these definitions is the following. Fix a node $x \in V(T)$. Then $\chi$ describes a 3-coloring of the vertices in the bag $X_x$, which is not necessarily a proper 3-coloring. The function $f(x, \chi)$ describes if $\chi$ can be extended to a proper 3-coloring of the vertices in the subtree of $T$ rooted at $x$.

Now, let $v \in V(G)$. Let $a, b \in V(T)$ such that $v$ is introduced at $a$, and $b$ is the child of $a$.

Let $\theta : X_a \to [3]$ be a function such that

$\forall y \in X_a \cap N_G(v) : \quad \big(\theta(y) \neq \theta(v)\big)$

In other words, $\theta$ is a three-coloring of $X_a$ which ensures that the color of $v$ is different from the color of any of its neighbors in $X_a$.

Let $\theta' : X_b \to [3]$ be defined as follows:

$\forall y \in X_b : \quad \theta'(y) := \theta(y)$

Note that $X_b = X_a \cup \{v\}$ and thus $\theta'$ is simply the projection of $\theta$ on $X_b$.

Let $w \in V(G)$. Let $c, d \in V(T)$ such that $w$ is forgotten at $c$, and $d$ is the child of $c$.

In other words, $X_c = X_d \setminus \{w\}$.

Let $\psi : X_c \to [3]$ be a function. For every $i \in [3]$, let $\psi'_i : X_d \to [3]$ be defined as follows:

$\begin{aligned} \forall y \in X_d \setminus \{w\} : \quad & \psi'_i(y) := \psi(y) \\ & \psi'_i(w) := i \end{aligned}$

To explain this, assume that $\psi$ is a given 3-coloring of the parent node $X_c$. Now we define three colorings that extend $\psi$ in the child node $X_d$. For a fixed color $i \in [3]$, we are coloring every vertex in $X_d$ other than $w$ in the same way that it was colored in $X_c$ under $\psi$, and we are coloring $w$ with color $i$.

Let $e, g, h \in V(T)$ such that $e$ is a join node, and $g$ and $h$ are the children of $e$, and let $\lambda : X_e \to [3]$.

Based on the above data, answer the given subquestions.

In this question, we use $[3]$ to denote $\{1, 2, 3\}$.

Let $G$ be a simple undirected finite graph. A function $f : V(G) \to [3]$ is called a proper 3-coloring of $G$ if no two adjacent vertices in $G$ have the same image under $f$. You can imagine $f$ coloring the vertices of the graph with colors 1, 2, and 3 (all vertices that have image 1 under $f$ are 'colored' 1, and so on); and such a coloring is proper if and only if there are no edges between vertices that have the same color.

In this question, we will explore ideas involving building up a DP-based solution for this problem for graphs of bounded treewidth using nice tree decompositions.

Let $\mathcal{T}(T, \{X_t\}_{t \in V(T)})$ be a rooted nice tree decomposition of $G$. For every node $t \in V(T)$, let $T_t$ denote the subtree of $T$ rooted at $t$.

For every node $x \in V(T)$ and every function $\chi : X_x \to [3]$, let $f(x, \chi)$ be defined as follows:

$f(x, \chi) := \text{TRUE}$ if there exists a function $\sigma : \bigcup_{\beta \in V(T_x)} X_\beta \to [3]$ such that

• $\forall u \in X_x : \ \big(\chi(u) = \sigma(u)\big)$
• No two adjacent vertices in $G\left[\bigcup_{\beta \in V(T_x)} X_\beta\right]$ have the same image under $\sigma$.

Otherwise, $f(x, \chi) := \text{FALSE}$.

The intuition for these definitions is the following. Fix a node $x \in V(T)$. Then $\chi$ describes a 3-coloring of the vertices in the bag $X_x$, which is not necessarily a proper 3-coloring. The function $f(x, \chi)$ describes if $\chi$ can be extended to a proper 3-coloring of the vertices in the subtree of $T$ rooted at $x$.

Now, let $v \in V(G)$. Let $a, b \in V(T)$ such that $v$ is introduced at $a$, and $b$ is the child of $a$.

Let $\theta : X_a \to [3]$ be a function such that

$\forall y \in X_a \cap N_G(v) : \quad \big(\theta(y) \neq \theta(v)\big)$

In other words, $\theta$ is a three-coloring of $X_a$ which ensures that the color of $v$ is different from the color of any of its neighbors in $X_a$.

Let $\theta' : X_b \to [3]$ be defined as follows:

$\forall y \in X_b : \quad \theta'(y) := \theta(y)$

Note that $X_b = X_a \cup \{v\}$ and thus $\theta'$ is simply the projection of $\theta$ on $X_b$.

Let $w \in V(G)$. Let $c, d \in V(T)$ such that $w$ is forgotten at $c$, and $d$ is the child of $c$.

In other words, $X_c = X_d \setminus \{w\}$.

Let $\psi : X_c \to [3]$ be a function. For every $i \in [3]$, let $\psi'_i : X_d \to [3]$ be defined as follows:

$\begin{aligned} \forall y \in X_d \setminus \{w\} : \quad & \psi'_i(y) := \psi(y) \\ & \psi'_i(w) := i \end{aligned}$

To explain this, assume that $\psi$ is a given 3-coloring of the parent node $X_c$. Now we define three colorings that extend $\psi$ in the child node $X_d$. For a fixed color $i \in [3]$, we are coloring every vertex in $X_d$ other than $w$ in the same way that it was colored in $X_c$ under $\psi$, and we are coloring $w$ with color $i$.

Let $e, g, h \in V(T)$ such that $e$ is a join node, and $g$ and $h$ are the children of $e$, and let $\lambda : X_e \to [3]$.

Based on the above data, answer the given subquestions.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

If the ILP is feasible, its optimal solution must be greater than or equal to 54.3

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

If the ILP is feasible, its optimal solution must be less than or equal to 54.3.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

It is possible that the ILP’s optimal solution (if it exists) will also be 54.3.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

The ILP is guaranteed to be feasible.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$, $1$, and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.