Advanced Algorithms · End Term · Sep 2023 · FN

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.

Choose the correct options

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack. Based on the above data, answer the given subquestions.

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack. Based on the above data, answer the given subquestions.

What is the answer if R = C = N and all the squares on the topmost row and rightmost column (i.e, a L-shape) are cut out?

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack. Based on the above data, answer the given subquestions.

Consider the following bipartite graph: the set A is composed of elements corresponding to every row of the board, while set B consists of the columns. For each row add edges to every column if the corresponding square is not cut out of the board. What does the answer correspond to in this graph?

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack. Based on the above data, answer the given subquestions.

What is the number of valid placements of N mutually non-attacking rooks if R = C = N and there are no cut out squares? Two placements are distinct if there is at least one square which has a rook in one of them and does not have a rook in the other.

Based on the above data, answer the given subquestions.

Which DP table entries do we lookup to find Π({a, c, d}, 3)?

Based on the above data, answer the given subquestions.

Which DP table entries do we lookup to find Π({a, b, c}, 2)?

The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalization of the popular Fibonacci numbers that you might expect):

Based on the above data, answer the given subquestions.

The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalization of the popular Fibonacci numbers that you might expect):

Based on the above data, answer the given subquestions.

The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalization of the popular Fibonacci numbers that you might expect):

Based on the above data, answer the given subquestions.

Consider the given statements and answer if they are true or false.

The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.

Consider the given statements and answer if they are true or false.

Answer the given subquestions.

Every linear program has a unique optimal solution.

Answer the given subquestions.

Answer the given subquestions.

Consider the algorithm in the previous question. Does the algorithm always output an optimal vertex cover?

Answer the given subquestions.

Consider the algorithm in the previous question. Does the algorithm always output a 2- approximate vertex cover?

Answer the given subquestions.

Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there examples of graphs where the size of the optimal vertex cover is **exactly** **equal** to twice the size of its maximum matching? For example, this is not true for a path on three vertices: the size of both the maximum matching and minimum vertex cover is 1.