Advanced Algorithms Quiz 1: 7 July 2024 (May 2024 term)

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the answer if the input is 1 1 2 1?

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the answer if the input is 1 2 3 4 5 6 7 8 9 10?

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the answer if 2n = 50 and the input is the set of all even numbers between 1 and 100? (Hint: you might want to use the fact that the sum of the first n odd numbers is n².)

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the general strategy for solving this problem? Select all strategies that are correct.

Alice and Bob play the following game using an array $a$ of $n$ integers:

1. Players take turns, Alice moves first.
2. Each turn a player chooses any element and removes it from the array.
3. If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
4. Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $n = 4$ and $a = [5, 2, 7, 3]$, then the game could go as follows (there are other options):

1. On the first move, Alice chooses 2 and get two points. Her score is now 2 . The array $a$ is now $[5, 7, 3]$.
2. On the second move, Bob chooses 5 and get five points. His score is now 5. The array $a$ is now [7,3].
3. On the third move, Alice chooses 7 and get no points. Her score is now 2. The array $a$ is now [3].
4. On the last move, Bob chooses 3 and get three points. His score is now 8 . The array $a$ is empty now.
5. Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally.

Note that there may be duplicate numbers in the array.

To play optimally means to play to force a win whenever possible.
Based on the above data answer the given subquestions.

Alice and Bob play the following game using an array $a$ of $n$ integers:

1. Players take turns, Alice moves first.
2. Each turn a player chooses any element and removes it from the array.
3. If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
4. Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $n = 4$ and $a = [5, 2, 7, 3]$, then the game could go as follows (there are other options):

1. On the first move, Alice chooses 2 and get two points. Her score is now 2 . The array $a$ is now $[5, 7, 3]$.
2. On the second move, Bob chooses 5 and get five points. His score is now 5. The array $a$ is now [7,3].
3. On the third move, Alice chooses 7 and get no points. Her score is now 2. The array $a$ is now [3].
4. On the last move, Bob chooses 3 and get three points. His score is now 8 . The array $a$ is empty now.
5. Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally.

Note that there may be duplicate numbers in the array.

To play optimally means to play to force a win whenever possible.
Based on the above data answer the given subquestions.

Alice and Bob play the following game using an array $a$ of $n$ integers:

1. Players take turns, Alice moves first.
2. Each turn a player chooses any element and removes it from the array.
3. If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
4. Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $n = 4$ and $a = [5, 2, 7, 3]$, then the game could go as follows (there are other options):

1. On the first move, Alice chooses 2 and get two points. Her score is now 2 . The array $a$ is now $[5, 7, 3]$.
2. On the second move, Bob chooses 5 and get five points. His score is now 5. The array $a$ is now [7,3].
3. On the third move, Alice chooses 7 and get no points. Her score is now 2. The array $a$ is now [3].
4. On the last move, Bob chooses 3 and get three points. His score is now 8 . The array $a$ is empty now.
5. Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally.

Note that there may be duplicate numbers in the array.

To play optimally means to play to force a win whenever possible.
Based on the above data answer the given subquestions.

Alice and Bob play the following game using an array $a$ of $n$ integers:

1. Players take turns, Alice moves first.
2. Each turn a player chooses any element and removes it from the array.
3. If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
4. Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $n = 4$ and $a = [5, 2, 7, 3]$, then the game could go as follows (there are other options):

1. On the first move, Alice chooses 2 and get two points. Her score is now 2 . The array $a$ is now $[5, 7, 3]$.
2. On the second move, Bob chooses 5 and get five points. His score is now 5. The array $a$ is now [7,3].
3. On the third move, Alice chooses 7 and get no points. Her score is now 2. The array $a$ is now [3].
4. On the last move, Bob chooses 3 and get three points. His score is now 8 . The array $a$ is empty now.
5. Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally.

Note that there may be duplicate numbers in the array.

To play optimally means to play to force a win whenever possible.
Based on the above data answer the given subquestions.

Alice and Bob play the following game using an array $a$ of $n$ integers:

1. Players take turns, Alice moves first.
2. Each turn a player chooses any element and removes it from the array.
3. If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
4. Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $n = 4$ and $a = [5, 2, 7, 3]$, then the game could go as follows (there are other options):

1. On the first move, Alice chooses 2 and get two points. Her score is now 2 . The array $a$ is now $[5, 7, 3]$.
2. On the second move, Bob chooses 5 and get five points. His score is now 5. The array $a$ is now [7,3].
3. On the third move, Alice chooses 7 and get no points. Her score is now 2. The array $a$ is now [3].
4. On the last move, Bob chooses 3 and get three points. His score is now 8 . The array $a$ is empty now.
5. Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally.

Note that there may be duplicate numbers in the array.

To play optimally means to play to force a win whenever possible.
Based on the above data answer the given subquestions.

Alice and Bob play the following game using an array $a$ of $n$ integers:

1. Players take turns, Alice moves first.
2. Each turn a player chooses any element and removes it from the array.
3. If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
4. Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $n = 4$ and $a = [5, 2, 7, 3]$, then the game could go as follows (there are other options):

1. On the first move, Alice chooses 2 and get two points. Her score is now 2 . The array $a$ is now $[5, 7, 3]$.
2. On the second move, Bob chooses 5 and get five points. His score is now 5. The array $a$ is now [7,3].
3. On the third move, Alice chooses 7 and get no points. Her score is now 2. The array $a$ is now [3].
4. On the last move, Bob chooses 3 and get three points. His score is now 8 . The array $a$ is empty now.
5. Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally.

Note that there may be duplicate numbers in the array.

To play optimally means to play to force a win whenever possible.
Based on the above data answer the given subquestions.

What is the general strategy for Alice?

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.

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

What is the answer if there are four flowers with heights 3, 1, 4, 2 and beauties 10, 20, 30, 40, respectively?

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

What is the answer if there are four flowers with heights 4, 3, 2, 1 and beauties 10, 20, 30, 40, respectively?

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

What is the answer if there are nine flowers with heights 4, 2, 5, 8, 3, 6, 1, 7, 9 and beauties 6, 8, 8, 4, 6, 3, 5, 7, 5, respectively?

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

Consider the following greedy algorithm for the problem: scan the flowers left to right. If the current flower violates the monotonicity condition with respect to the sequence we have so far, remove it. Otherwise, keep it. Is this algorithm correct?

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

Consider the following greedy algorithm for the problem:
Phase 1. scan the flowers left to right. If the current flower violates the monotonicity condition (increasing heights) with respect to the sequence we have so far, remove it. Otherwise, keep it. At the end, suppose the total beauty of the remaining flowers is p.
Phase 2. Starting with the original set of flowers again, scan them right to left. If the current flower violates the monotonicity condition (decreasing heights) with respect to the sequence we have so far, remove it. Otherwise, keep it. At the end, suppose the total beauty of the remaining flowers is q.
Return max(p, q). Is this algorithm correct?

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

Consider the following greedy algorithm for the problem. Initially, all flowers are unmarked. Repeat until a monotonically increasing sequence is obtained: keep and mark the most beautiful unmarked flower, and remove all flowers taller than it to its left and shorter than it to its right. Is this algorithm correct?

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

There are $N$ flowers arranged in a row. For each $i(1 \leq i \leq n)$, the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively.

Here, $h_1, h_2, \ldots, h_n$ are all distinct.

You are pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

The goal is to remove flowers in a manner that maximizes the sum of the beauties of the remaining flowers.

The optimal solution to a given instance of this problem is the maximum obtainable sum of beauties under the constraint that the heights have to be monotonically increasing from left to right.

Based on the above data answer the given subquestions.

The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him.
For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game.
Based on the above data answer the given subquestions.

How many cops are necessary and sufficient to catch the robber on a path?

The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him.
For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game.
Based on the above data answer the given subquestions.

How many cops are necessary and sufficient to catch the robber on a tree?

The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him.
For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game.
Based on the above data answer the given subquestions.

How many cops are necessary and sufficient to catch the robber on a cycle?

The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him.
For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game.
Based on the above data answer the given subquestions.

How many cops are definitely enough to catch the robber on a graph of treewidth k?