Advanced Algorithms · Quiz 1 · May 2024

Based on the above data answer the given subquestions.

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

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?

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\(^{2}\).)

Based on the above data answer the given subquestions.

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

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

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

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

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

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

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.

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?

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?

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?

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?

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?

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?

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.

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?