Which of the following statements is true?
Statement 1: For every graph G and every maximum flow on G, there always exists an edge such
that increasing the capacity on that edge will increase the maximum flow that’s possible in the
graph.
Statement 2: Suppose the maximum (s,t)-flow of some graph has value f. Now we increase the
capacity of every edge by 1. Then the maximum (s,t)-flow in this modified graph will have value at
most f + 1.
6406533053186.
Statement 1
6406533053187.
Statement 2
6406533053188.
Both statements
6406533053189.
Neither statement
A published solution is not available for this question yet.
A subset S of vertices in an undirected graph G is half-independent if each vertex in S is adjacent to
at most one other vertex in S. Is it true that finding the size of the largest half-independent set of
vertices in a given undirected graph is NP-hard?
6406533053248.
Yes, this can be shown by a reduction from the standard maximum
independent set problem.
6406533053249.
Yes, and this can be shown by reducing the half-independent set problem to
the standard maximum independent set problem.
6406533053250.
No, the problem of finding a largest half-independent set of vertices is in P
since it can be reduced to the problem of finding a maximum matching.
A published solution is not available for this question yet.
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?
6406533053125.
0
6406533053126.
1
6406533053127.
2
6406533053128.
3
A published solution is not available for this question yet.
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?
6406533053129.
10
6406533053130.
15
6406533053131.
17
6406533053132.
18
A published solution is not available for this question yet.
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?
A published solution is not available for this question yet.
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?
6406533053134.
The target sum is less than the number of dice.
6406533053135.
The target sum is greater than SN, the product of the number of dice and the
number of sides.
6406533053136.
The target sum is not divisible by the number of dice.
6406533053137.
The target sum is equal to the number of dice.
A published solution is not available for this question yet.
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?
6406533053138.
0, 1, 2, 3, 4, 5, 6
6406533053139.
1, 2, 3, 4, 5, 6
6406533053140.
1, 2, 3, 4, 5, 6, 7
6406533053141.
0, 1, 2, 3, 4, 5, 6, 7
A published solution is not available for this question yet.
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.
Let DP[N,T ] denote the number of ways to achieve a target sum of T > 0 using N > 0 dice. Which of
the following recursive formulas is correct if all the dice have S sides?
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]?
A published solution is not available for this question yet.
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, T ] for any T > 0?
A published solution is not available for this question yet.
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[N , 0] for any N > 0?
A published solution is not available for this question yet.
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[N , T ] if T < N ?
A published solution is not available for this question yet.
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 this given subquestion, we will examine the relationship of treewidth with other graph
parameters.
Let G be an undirected connected graph and T be a depth-first search (DFS) tree of G rooted at a
vertex r. An edge of G is called a back edge if the endpoints of the edge are on the same root to
leaf path in T . That is, an edge is from a vertex to one of its ancestors in the DFS tree. An edge that
is not a back edge is called a cross edge. Indeed, such an edge points from a vertex to a previously
visited vertex that is neither an ancestor nor a descendant. Which of the following statements are
true?
6406533053168.
There are no back edges in G.
6406533053169.
There are no cross edges in G.
6406533053170.
DFS can be used to test whether G has a Hamiltonian path.
6406533053171.
The set of leaves of T forms an independent set in G.
A published solution is not available for this question yet.
In this given subquestion, we will examine the relationship of treewidth with other graph
parameters.
Let G be an undirected connected graph and T be a depth-first search (DFS) tree of G rooted at a
vertex r. Depth of T is the length of a longest path from root to a leaf. Let q be the depth of T .
Which of the following statements are true?
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
6406533053197.
TRUE
6406533053198.
FALSE
A published solution is not available for this question yet.
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.
6406533053199.
TRUE
6406533053200.
FALSE
A published solution is not available for this question yet.
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 be 50 ×10\(^{2331}\).
6406533053201.
TRUE
6406533053202.
FALSE
A published solution is not available for this question yet.
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.
6406533053203.
TRUE
6406533053204.
FALSE
A published solution is not available for this question yet.
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.
6406533053205.
TRUE
6406533053206.
FALSE
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to
at least two vertices in S which are in different cliques, then we can delete it and leave the
parameter unchanged.
6406533053234.
TRUE
6406533053235.
FALSE
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to
at least two vertices in S which are in different cliques, then we can delete it and decrease the
parameter by 1.
6406533053236.
TRUE
6406533053237.
FALSE
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to
some but not all vertices in a clique of G[S], then we can delete it and leave the parameter
unchanged.
6406533053238.
TRUE
6406533053239.
FALSE
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to
some but not all vertices in a clique of G[S], then we can delete it and decrease the parameter by 1.
6406533053240.
TRUE
6406533053241.
FALSE
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
6406533053246.
TRUE
6406533053247.
FALSE
**OS**
**Section Id :** 64065364233
**Section Number :** 15
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 21
**Number of Questions to be attempted :** 21
**Section Marks :** 50
**Display Number Panel :** Yes
**Section Negative Marks :** 0
**Group All Questions :** No
**Enable Mark as Answered Mark for Review and**
No
**Clear Response :**
**Maximum Instruction Time :** 0
A published solution is not available for this question yet.
