cs4021_2026T1_ET_FN.pdf
Advanced Algorithms · End Term · Jan 2026 FN
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 2 MCQ · 1.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
Can the disk with dimensions [2,1,2] be placed above [3,2,3]?
Yes
No
A published solution is not available for this question yet.
Question 3 MCQ · 1.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
Can the disk with dimensions [2,2,2] be placed above [3,2,3]?
Yes
No
A published solution is not available for this question yet.
Question 4 NAT · 2.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
Suppose the input consists of the following triplets: [[3, 5, 7], [3, 2, 2], [3, 1, 1], [5, 5, 9]]. What's the
answer?
A published solution is not available for this question yet.
Question 5 MCQ · 2.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
Our approach will be to building a DP table of the same length as the array of disks. Let [[IMAGE:4db73861b8381146_3_4]] denote
the [[IMAGE:4db73861b8381146_3_5]] disk in the input array. The value of DP [[IMAGE:4db73861b8381146_3_6]] will be the height of the tallest tower that can be
created with [[IMAGE:4db73861b8381146_3_7]] the bottom. We initialize the value of DP [[IMAGE:4db73861b8381146_3_8]] to the height of [[IMAGE:4db73861b8381146_3_9]] .
Consider the following approach. We process the DP array in increasing order of indices (i.e, [[IMAGE:4db73861b8381146_3_10]]
to [[IMAGE:4db73861b8381146_3_11]] ). We look at all disks [[IMAGE:4db73861b8381146_3_12]] where [[IMAGE:4db73861b8381146_3_13]] and [[IMAGE:4db73861b8381146_3_14]] can be placed on top of [[IMAGE:4db73861b8381146_3_15]] . If [[IMAGE:4db73861b8381146_3_16]] can be
placed on top of [[IMAGE:4db73861b8381146_3_17]] , then DP [[IMAGE:4db73861b8381146_3_18]] is updated to be the maximum of DP [[IMAGE:4db73861b8381146_3_19]] and DP [[IMAGE:4db73861b8381146_3_20]] , where [[IMAGE:4db73861b8381146_3_21]] is
the height of the disk [[IMAGE:4db73861b8381146_3_22]] .
What can you say about this approach?
This approach is correct.
This approach is incorrect, because we might miss some disks that can be
placed on top of [[IMAGE:4db73861b8381146_3_23]] , as the given array may not be sorted by height.
This approach is incorrect because the values we are looking up may not be
computed correctly when we need them.
A published solution is not available for this question yet.
Question 6 MCQ · 2.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
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, [[IMAGE:4db73861b8381146_4_24]] to [[IMAGE:4db73861b8381146_4_25]] ). We look at all disks [[IMAGE:4db73861b8381146_4_26]]
such that [[IMAGE:4db73861b8381146_4_27]] can be placed on top of [[IMAGE:4db73861b8381146_4_28]] . If [[IMAGE:4db73861b8381146_4_29]] can be placed on top of [[IMAGE:4db73861b8381146_4_30]] , then DP [[IMAGE:4db73861b8381146_4_31]] is updated to
be the maximum of DP [[IMAGE:4db73861b8381146_4_32]] and DP [[IMAGE:4db73861b8381146_4_33]] , where [[IMAGE:4db73861b8381146_4_34]] is the height of the disk [[IMAGE:4db73861b8381146_4_35]] .
Note that the DP array is initialized as before, that is, DP [[IMAGE:4db73861b8381146_4_36]] is initialized to the height of [[IMAGE:4db73861b8381146_4_37]] .
What can you say about this approach?
This approach is correct.
This approach is incorrect, because we might miss some disks that can be
placed on top of [[IMAGE:4db73861b8381146_4_38]] , as the given array may not be sorted by height.
This approach is incorrect because the values we are looking up may not be
computed correctly when we need them.
A published solution is not available for this question yet.
Question 7 MCQ · 2.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
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, [[IMAGE:4db73861b8381146_4_39]] is a disk that has the
smallest height, while [[IMAGE:4db73861b8381146_4_40]] is a disk that has the largest height.
We process the DP array in increasing order of indices (i.e, [[IMAGE:4db73861b8381146_4_41]] to [[IMAGE:4db73861b8381146_4_42]] ). We look at all disks [[IMAGE:4db73861b8381146_4_43]]
where [[IMAGE:4db73861b8381146_4_44]] such that [[IMAGE:4db73861b8381146_4_45]] can be placed on top of [[IMAGE:4db73861b8381146_4_46]] . If [[IMAGE:4db73861b8381146_4_47]] can be placed on top of [[IMAGE:4db73861b8381146_4_48]] , then DP [[IMAGE:4db73861b8381146_4_49]] is
updated to be the maximum of DP [[IMAGE:4db73861b8381146_4_50]] and DP [[IMAGE:4db73861b8381146_4_51]] , where [[IMAGE:4db73861b8381146_4_52]] is the height of the disk [[IMAGE:4db73861b8381146_4_53]] .
What can you say about this approach?
This approach is correct.
This approach is incorrect, because we might miss some disks that can be
placed on top of [[IMAGE:4db73861b8381146_4_54]] , as the given array may not be sorted by height.
This approach is incorrect because the values we are looking up may not be
computed correctly when we need them.
A published solution is not available for this question yet.
Question 8 MCQ · 2.0 marks
We are given a non-empty list of [[IMAGE:4db73861b8381146_2_2]] 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 [[IMAGE:4db73861b8381146_2_3]] -based indexing in the
subquestions given.
What is the complexity of this algorithm?
[[IMAGE:4db73861b8381146_5_55]]
[[IMAGE:4db73861b8381146_5_56]]
[[IMAGE:4db73861b8381146_5_57]]
[[IMAGE:4db73861b8381146_5_58]]
A published solution is not available for this question yet.
Question 9 MCQ · 3.0 marks
Answer the given subquestions about matroids.
The rank function of a matroid [[IMAGE:4db73861b8381146_5_59]] , denoted by either [[IMAGE:4db73861b8381146_5_60]] or [[IMAGE:4db73861b8381146_5_61]] , is defined by:
[[IMAGE:4db73861b8381146_5_62]]
Does the rank function satisfy the following property for any pair of subsets [[IMAGE:4db73861b8381146_5_63]] ?
[[IMAGE:4db73861b8381146_5_64]]
Yes
No
A published solution is not available for this question yet.
Question 10 MCQ · 2.0 marks
Answer the given subquestions about matroids.
Let [[IMAGE:4db73861b8381146_6_65]] be a matroid and let
[[IMAGE:4db73861b8381146_6_66]]
where [[IMAGE:4db73861b8381146_6_67]] .
This is the set system obtained by "removing" an element [[IMAGE:4db73861b8381146_6_68]] from [[IMAGE:4db73861b8381146_6_69]] . Is [[IMAGE:4db73861b8381146_6_70]] also a matroid?
True
False
A published solution is not available for this question yet.
Question 11 MSQ · 2.0 marks
Answer the given subquestions about matroids.
Choose the correct option(s):
Let [[IMAGE:4db73861b8381146_6_71]] . Let
[[IMAGE:4db73861b8381146_6_72]] . Then, [[IMAGE:4db73861b8381146_6_73]] is a
matroid.
Let [[IMAGE:4db73861b8381146_6_74]] and [[IMAGE:4db73861b8381146_6_75]] be the collection of all subsets of [[IMAGE:4db73861b8381146_6_76]] with at
least [[IMAGE:4db73861b8381146_6_77]] elements. Then [[IMAGE:4db73861b8381146_6_78]] together form a matroid.
A published solution is not available for this question yet.
Question 12 MCQ · 1.0 marks
Consider a universe [[IMAGE:4db73861b8381146_6_79]] of [[IMAGE:4db73861b8381146_6_80]] couples. A subset [[IMAGE:4db73861b8381146_6_81]] is good if it has at most
three couples in it. Consider the family of all good sets. What can you say about this family?
Based on the above data, answer the given subquestions.
The family satisfies the heriditary property, that is, if [[IMAGE:4db73861b8381146_7_82]] is a good set and [[IMAGE:4db73861b8381146_7_83]] , then [[IMAGE:4db73861b8381146_7_84]] is also a
good set.
True
False
A published solution is not available for this question yet.
Question 13 MCQ · 2.0 marks
Consider a universe [[IMAGE:4db73861b8381146_6_79]] of [[IMAGE:4db73861b8381146_6_80]] couples. A subset [[IMAGE:4db73861b8381146_6_81]] is good if it has at most
three couples in it. Consider the family of all good sets. What can you say about this family?
Based on the above data, answer the given subquestions.
Consider two good sets [[IMAGE:4db73861b8381146_7_85]] and [[IMAGE:4db73861b8381146_7_86]] where [[IMAGE:4db73861b8381146_7_87]] and [[IMAGE:4db73861b8381146_7_88]] . Then there exists an element
[[IMAGE:4db73861b8381146_7_89]] such that [[IMAGE:4db73861b8381146_7_90]] is a good set.
True
False
A published solution is not available for this question yet.
Question 14 MCQ · 2.0 marks
Consider a universe [[IMAGE:4db73861b8381146_6_79]] of [[IMAGE:4db73861b8381146_6_80]] couples. A subset [[IMAGE:4db73861b8381146_6_81]] is good if it has at most
three couples in it. Consider the family of all good sets. What can you say about this family?
Based on the above data, answer the given subquestions.
Recall that the exchange property is the following. If [[IMAGE:4db73861b8381146_7_91]] and [[IMAGE:4db73861b8381146_7_92]] are good sets and [[IMAGE:4db73861b8381146_7_93]] then
there exists an element [[IMAGE:4db73861b8381146_7_94]] such that [[IMAGE:4db73861b8381146_7_95]] is a good set. The family of all good sets
satisfies the exchange property. Note that we make no assumption about [[IMAGE:4db73861b8381146_7_96]] unlike the
previous question.
True
False
A published solution is not available for this question yet.
Question 15 MSQ · 3.0 marks
In this question, we will examine the relationship of treewidth with other graph parameters.
Let [[IMAGE:4db73861b8381146_7_97]] be an undirected connected graph and [[IMAGE:4db73861b8381146_7_98]] be a depth-first search (DFS) tree of [[IMAGE:4db73861b8381146_7_99]] rooted at a
vertex [[IMAGE:4db73861b8381146_8_100]] . Depth of [[IMAGE:4db73861b8381146_8_101]] is the length of a longest path from root to a leaf. Let [[IMAGE:4db73861b8381146_8_102]] be the depth of [[IMAGE:4db73861b8381146_8_103]] .
Which of the following statements are true?
Treewidth of [[IMAGE:4db73861b8381146_8_104]] is at most [[IMAGE:4db73861b8381146_8_105]] .
Pathwidth of [[IMAGE:4db73861b8381146_8_106]] is at most [[IMAGE:4db73861b8381146_8_107]] .
There is no relation between [[IMAGE:4db73861b8381146_8_108]] and the treewidth of [[IMAGE:4db73861b8381146_8_109]] .
Maximum Independent Set can be solved in time [[IMAGE:4db73861b8381146_8_110]] .
A published solution is not available for this question yet.
Question 16 MCQ · 2.0 marks
In this question, we will examine the relationship of treewidth with other graph parameters.
What is the treewidth of [[IMAGE:4db73861b8381146_8_111]] , a simple cycle on [[IMAGE:4db73861b8381146_8_112]] vertices?
One
Two
One if [[IMAGE:4db73861b8381146_8_113]] is odd and two if [[IMAGE:4db73861b8381146_8_114]] is even
[[IMAGE:4db73861b8381146_8_115]]
[[IMAGE:4db73861b8381146_8_116]]
[[IMAGE:4db73861b8381146_8_117]]
A published solution is not available for this question yet.
Question 17 MCQ · 3.0 marks
Recall the max-flow problem: for a directed graph [[IMAGE:4db73861b8381146_8_118]] with non-negative capacities [[IMAGE:4db73861b8381146_8_119]] for
every
[[IMAGE:4db73861b8381146_9_120]] and two special vertices [[IMAGE:4db73861b8381146_9_121]] (source, with no incoming edges) and [[IMAGE:4db73861b8381146_9_122]] (sink, with no outgoing
edges), a flow in [[IMAGE:4db73861b8381146_9_123]] is an assignment [[IMAGE:4db73861b8381146_9_124]] such that [[IMAGE:4db73861b8381146_9_125]] for every edge and for every
vertex [[IMAGE:4db73861b8381146_9_126]] . The task is to find a maximum flow (f) i.e.,
a flow (f) such that [[IMAGE:4db73861b8381146_9_127]] is maximized.
Given an instance [[IMAGE:4db73861b8381146_9_128]] , we attempt here to design a LP whose optimal value is equal to the
maximum flow in the graph [[IMAGE:4db73861b8381146_9_129]] . There is a variable [[IMAGE:4db73861b8381146_9_130]] for all [[IMAGE:4db73861b8381146_9_131]] . Note that for any pair of
vertices that is not an edge, we do not introduce any variable corresponding to it.
[[IMAGE:4db73861b8381146_9_132]]
Is the LP above a valid formulation for computing the maximum flow in [[IMAGE:4db73861b8381146_9_133]] ?
Yes, this is a valid set of constraints.
No, the sum in the objective function should be taken only over neighbors of [[IMAGE:4db73861b8381146_9_134]]
.
No, the sum in the second constraint should be taken only over in-neighbors
of [[IMAGE:4db73861b8381146_9_135]] and out-neighbors of [[IMAGE:4db73861b8381146_9_136]] , respectively.
A published solution is not available for this question yet.
Question 18 MCQ · 3.0 marks
Given a flow network [[IMAGE:4db73861b8381146_9_137]] and a flow [[IMAGE:4db73861b8381146_9_138]] , how will you determine if [[IMAGE:4db73861b8381146_9_139]] is maximum flow?
If there is any edge that is not saturated to full capacity, then we can conclude
that [[IMAGE:4db73861b8381146_9_140]] is not a maximum flow.
If the residual graph does not have any augmenting paths then [[IMAGE:4db73861b8381146_9_141]] is a
maximum flow.
If the value of the flow [[IMAGE:4db73861b8381146_10_142]] is not the sum of the capacities of the edges coming
out of the source [[IMAGE:4db73861b8381146_10_143]] then [[IMAGE:4db73861b8381146_10_144]] is not a maximum flow.
If the value of the flow [[IMAGE:4db73861b8381146_10_145]] is not the sum of the capacities of the edges coming
into the sink [[IMAGE:4db73861b8381146_10_146]] then [[IMAGE:4db73861b8381146_10_147]] is not a maximum flow.
A published solution is not available for this question yet.
Question 19 MCQ · 2.0 marks
Consider the LP for vertex cover for the graph [[IMAGE:4db73861b8381146_10_148]] shown in the figure below.
[[IMAGE:4db73861b8381146_10_149]]
Based on the above data, answer the given subquestions.
The value of the optimal solution for the Vertex Cover LP corresponding to [[IMAGE:4db73861b8381146_10_150]] is less than 2.
True
False
A published solution is not available for this question yet.
Question 20 MCQ · 2.0 marks
Consider the LP for vertex cover for the graph [[IMAGE:4db73861b8381146_10_148]] shown in the figure below.
[[IMAGE:4db73861b8381146_10_149]]
Based on the above data, answer the given subquestions.
The value of the optimal solution for the Vertex Cover LP corresponding to [[IMAGE:4db73861b8381146_11_151]] is 2.
True
False
A published solution is not available for this question yet.
Question 21 MCQ · 2.0 marks
Consider the LP for vertex cover for the graph [[IMAGE:4db73861b8381146_10_148]] shown in the figure below.
[[IMAGE:4db73861b8381146_10_149]]
Based on the above data, answer the given subquestions.
The size of the smallest vertex cover of [[IMAGE:4db73861b8381146_11_152]] is 2.
True
False
A published solution is not available for this question yet.
Question 22 MCQ · 2.0 marks
Consider the LP for vertex cover for the graph [[IMAGE:4db73861b8381146_10_148]] shown in the figure below.
[[IMAGE:4db73861b8381146_10_149]]
Based on the above data, answer the given subquestions.
The all- [[IMAGE:4db73861b8381146_11_153]] solution is optimal for the Vertex Cover LP corresponding to [[IMAGE:4db73861b8381146_11_154]] .
True
False
A published solution is not available for this question yet.
Question 23 MCQ · 2.0 marks
Consider the LP for vertex cover for the graph [[IMAGE:4db73861b8381146_10_148]] shown in the figure below.
[[IMAGE:4db73861b8381146_10_149]]
Based on the above data, answer the given subquestions.
After deleting the vertex [[IMAGE:4db73861b8381146_11_155]] from [[IMAGE:4db73861b8381146_11_156]] , the value of the optimal LP solution decreases by 1.
True
False
A published solution is not available for this question yet.
Question 24 MCQ · 2.0 marks
Let [[IMAGE:4db73861b8381146_11_157]] be a graph with positive edge weights. Then its aspect ratio is the quantity
[[IMAGE:4db73861b8381146_12_158]] .
Given a graph [[IMAGE:4db73861b8381146_12_159]] , a reweighted graph on the same vertex and edge set
[[IMAGE:4db73861b8381146_12_160]] is **shortest-paths preserving** if, for every shortest path [[IMAGE:4db73861b8381146_12_161]] in [[IMAGE:4db73861b8381146_12_162]] , the sequence of
nodes and edges along [[IMAGE:4db73861b8381146_12_163]] is also a shortest path in [[IMAGE:4db73861b8381146_12_164]] .
Based on the above data, answer the given subquestions.
Consider the following graphs [[IMAGE:4db73861b8381146_12_165]] and [[IMAGE:4db73861b8381146_12_166]] . Note that [[IMAGE:4db73861b8381146_12_167]] has aspect ratio [[IMAGE:4db73861b8381146_12_168]] and [[IMAGE:4db73861b8381146_12_169]] has aspect ratio
[[IMAGE:4db73861b8381146_12_170]] . Is [[IMAGE:4db73861b8381146_12_171]] shortest-paths preserving with respect to [[IMAGE:4db73861b8381146_12_172]] ?
[[IMAGE:4db73861b8381146_12_173]]
Yes
No
A published solution is not available for this question yet.
Question 25 MCQ · 2.0 marks
Let [[IMAGE:4db73861b8381146_11_157]] be a graph with positive edge weights. Then its aspect ratio is the quantity
[[IMAGE:4db73861b8381146_12_158]] .
Given a graph [[IMAGE:4db73861b8381146_12_159]] , a reweighted graph on the same vertex and edge set
[[IMAGE:4db73861b8381146_12_160]] is **shortest-paths preserving** if, for every shortest path [[IMAGE:4db73861b8381146_12_161]] in [[IMAGE:4db73861b8381146_12_162]] , the sequence of
nodes and edges along [[IMAGE:4db73861b8381146_12_163]] is also a shortest path in [[IMAGE:4db73861b8381146_12_164]] .
Based on the above data, answer the given subquestions.
Suppose you reweight the graph [[IMAGE:4db73861b8381146_12_174]] shown below on the left to the graph (H) on the right. Suppose
[[IMAGE:4db73861b8381146_12_175]] is shortest-paths preserving. Then what can you say about [[IMAGE:4db73861b8381146_12_176]] ?
[[IMAGE:4db73861b8381146_12_177]]
[[IMAGE:4db73861b8381146_13_178]]
[[IMAGE:4db73861b8381146_13_179]]
[[IMAGE:4db73861b8381146_13_180]]
[[IMAGE:4db73861b8381146_13_181]]
A published solution is not available for this question yet.
Question 26 MCQ · 2.0 marks
Let [[IMAGE:4db73861b8381146_11_157]] be a graph with positive edge weights. Then its aspect ratio is the quantity
[[IMAGE:4db73861b8381146_12_158]] .
Given a graph [[IMAGE:4db73861b8381146_12_159]] , a reweighted graph on the same vertex and edge set
[[IMAGE:4db73861b8381146_12_160]] is **shortest-paths preserving** if, for every shortest path [[IMAGE:4db73861b8381146_12_161]] in [[IMAGE:4db73861b8381146_12_162]] , the sequence of
nodes and edges along [[IMAGE:4db73861b8381146_12_163]] is also a shortest path in [[IMAGE:4db73861b8381146_12_164]] .
Based on the above data, answer the given subquestions.
Consider any reweighted graph [[IMAGE:4db73861b8381146_13_182]] of [[IMAGE:4db73861b8381146_13_183]] that is shortest-paths preserving, where [[IMAGE:4db73861b8381146_13_184]] is the graph
from part (b). Then the aspect ratio of [[IMAGE:4db73861b8381146_13_185]] :
is strictly more than [[IMAGE:4db73861b8381146_13_186]] for any reweighting
can be made at most [[IMAGE:4db73861b8381146_13_187]] for some reweighting
A published solution is not available for this question yet.
Question 27 MCQ · 2.0 marks
Let [[IMAGE:4db73861b8381146_11_157]] be a graph with positive edge weights. Then its aspect ratio is the quantity
[[IMAGE:4db73861b8381146_12_158]] .
Given a graph [[IMAGE:4db73861b8381146_12_159]] , a reweighted graph on the same vertex and edge set
[[IMAGE:4db73861b8381146_12_160]] is **shortest-paths preserving** if, for every shortest path [[IMAGE:4db73861b8381146_12_161]] in [[IMAGE:4db73861b8381146_12_162]] , the sequence of
nodes and edges along [[IMAGE:4db73861b8381146_12_163]] is also a shortest path in [[IMAGE:4db73861b8381146_12_164]] .
Based on the above data, answer the given subquestions.
Consider the following claim: for any DAG [[IMAGE:4db73861b8381146_13_188]] , it is possible to always find a re-weighting that is
shortest-paths preserving such that the aspect ratio with the new weight function is at most [[IMAGE:4db73861b8381146_13_189]] ,
where [[IMAGE:4db73861b8381146_13_190]] is the number of vertices in [[IMAGE:4db73861b8381146_13_191]] . Is this claim true?
True
False
A published solution is not available for this question yet.
Question 28 MCQ · 2.0 marks
Let [[IMAGE:4db73861b8381146_11_157]] be a graph with positive edge weights. Then its aspect ratio is the quantity
[[IMAGE:4db73861b8381146_12_158]] .
Given a graph [[IMAGE:4db73861b8381146_12_159]] , a reweighted graph on the same vertex and edge set
[[IMAGE:4db73861b8381146_12_160]] is **shortest-paths preserving** if, for every shortest path [[IMAGE:4db73861b8381146_12_161]] in [[IMAGE:4db73861b8381146_12_162]] , the sequence of
nodes and edges along [[IMAGE:4db73861b8381146_12_163]] is also a shortest path in [[IMAGE:4db73861b8381146_12_164]] .
Based on the above data, answer the given subquestions.
Consider the following claim: for any DAG [[IMAGE:4db73861b8381146_13_192]] , it is possible to always find a re-weighting that is
shortest-paths preserving such that the aspect ratio with the new weight function is at most [[IMAGE:4db73861b8381146_13_193]]
, where [[IMAGE:4db73861b8381146_13_194]] is the number of vertices in [[IMAGE:4db73861b8381146_13_195]] . Is this claim true?
True
False
A published solution is not available for this question yet.
Question 29 MCQ · 2.0 marks
Suppose we are given an ILP which seeks to minimize an objective function subject to constraints.
We solve the LP relaxation and find an optimal solution with the objective evaluating to [[IMAGE:4db73861b8381146_14_196]] .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 [[IMAGE:4db73861b8381146_14_197]] .
True
False
A published solution is not available for this question yet.
Question 30 MCQ · 2.0 marks
Suppose we are given an ILP which seeks to minimize an objective function subject to constraints.
We solve the LP relaxation and find an optimal solution with the objective evaluating to [[IMAGE:4db73861b8381146_14_196]] .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 [[IMAGE:4db73861b8381146_14_198]] .
True
False
A published solution is not available for this question yet.
Question 31 MCQ · 2.0 marks
Suppose we are given an ILP which seeks to minimize an objective function subject to constraints.
We solve the LP relaxation and find an optimal solution with the objective evaluating to [[IMAGE:4db73861b8381146_14_196]] .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 [[IMAGE:4db73861b8381146_14_199]] .
True
False
A published solution is not available for this question yet.
Question 32 MCQ · 2.0 marks
Suppose we are given an ILP which seeks to minimize an objective function subject to constraints.
We solve the LP relaxation and find an optimal solution with the objective evaluating to [[IMAGE:4db73861b8381146_14_196]] .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 [[IMAGE:4db73861b8381146_15_200]] .
True
False
A published solution is not available for this question yet.
Question 33 MCQ · 2.0 marks
Suppose we are given an ILP which seeks to minimize an objective function subject to constraints.
We solve the LP relaxation and find an optimal solution with the objective evaluating to [[IMAGE:4db73861b8381146_14_196]] .What
can you say about the original ILP?
Based on the above data, answer the given subquestions.
The ILP is guaranteed to be feasible.
True
False
A published solution is not available for this question yet.
Question 34 MCQ · 3.0 marks
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.
True
False
A published solution is not available for this question yet.
Question 35 MCQ · 3.0 marks
Consider the given statements and answer if they are true or false.
An adversary can provide randomized quicksort with an input array of length [[IMAGE:4db73861b8381146_15_201]] that forces the
algorithm to run in [[IMAGE:4db73861b8381146_15_202]] time on that input. (If you are not familiar with the [[IMAGE:4db73861b8381146_15_203]] asymptotic
notation, it roughly translates as "at least". For example, we can say that it is possible to come up
with an input that forces insertion sort to run for [[IMAGE:4db73861b8381146_16_204]] steps.)
True
False
A published solution is not available for this question yet.
Question 36 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
A graph [[IMAGE:4db73861b8381146_16_221]] is a cluster graph if and only if it does not have an induced path on [[IMAGE:4db73861b8381146_16_222]] vertices.
True
False
A published solution is not available for this question yet.
Question 37 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on [[IMAGE:4db73861b8381146_17_223]] is not a cluster
graph, we can immediately return YES.
True
False
A published solution is not available for this question yet.
Question 38 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of [[IMAGE:4db73861b8381146_17_224]]
is not a cluster graph, we can immediately return NO.
True
False
A published solution is not available for this question yet.
Question 39 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
If the subgraph induced on the vertices of [[IMAGE:4db73861b8381146_17_225]] is a cluster graph and a vertex in [[IMAGE:4db73861b8381146_17_226]] is
adjacent to at least two vertices in [[IMAGE:4db73861b8381146_17_227]] which are in different cliques, then we can delete it and leave
the parameter unchanged.
True
False
A published solution is not available for this question yet.
Question 40 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
If the subgraph induced on the vertices of [[IMAGE:4db73861b8381146_17_228]] is a cluster graph and a vertex in [[IMAGE:4db73861b8381146_17_229]] is
adjacent to at least two vertices in [[IMAGE:4db73861b8381146_17_230]] which are in different cliques, then we can delete it and
decrease the parameter by [[IMAGE:4db73861b8381146_17_231]] .
True
False
A published solution is not available for this question yet.
Question 41 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
If the subgraph induced on the vertices of [[IMAGE:4db73861b8381146_18_232]] is a cluster graph and a vertex in [[IMAGE:4db73861b8381146_18_233]] is
adjacent to some but not all vertices in a clique of [[IMAGE:4db73861b8381146_18_234]] , then we can delete it and leave the
parameter unchanged.
True
False
A published solution is not available for this question yet.
Question 42 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
If the subgraph induced on the vertices of [[IMAGE:4db73861b8381146_18_235]] is a cluster graph and a vertex in [[IMAGE:4db73861b8381146_18_236]] is
adjacent to some but not all vertices in a clique of [[IMAGE:4db73861b8381146_18_237]] , then we can delete it and decrease the
parameter by [[IMAGE:4db73861b8381146_18_238]] .
True
False
A published solution is not available for this question yet.
Question 43 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a
matching problem on a bipartite graph.
True
False
A published solution is not available for this question yet.
Question 44 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
DISJOINT CLUSTER VERTEX DELETION is NP-Hard.
True
False
A published solution is not available for this question yet.
Question 45 MCQ · 2.0 marks
A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a
graph where every vertex is adjacent to every other vertex.
The CLUSTER VERTEX DELETION problem is the following: Given an input graph [[IMAGE:4db73861b8381146_16_205]] and a
parameter [[IMAGE:4db73861b8381146_16_206]] , does there exist a set [[IMAGE:4db73861b8381146_16_207]] of at most [[IMAGE:4db73861b8381146_16_208]] vertices of [[IMAGE:4db73861b8381146_16_209]] such that the subgraph induced
on [[IMAGE:4db73861b8381146_16_210]] is a cluster graph.
In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph [[IMAGE:4db73861b8381146_16_211]] , parameter [[IMAGE:4db73861b8381146_16_212]]
and a set [[IMAGE:4db73861b8381146_16_213]] of vertices of [[IMAGE:4db73861b8381146_16_214]] of size [[IMAGE:4db73861b8381146_16_215]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_216]] is a cluster
graph. We need to find if there exists a subset [[IMAGE:4db73861b8381146_16_217]] of size at most [[IMAGE:4db73861b8381146_16_218]] which is disjoint from
[[IMAGE:4db73861b8381146_16_219]] such that the subgraph induced on [[IMAGE:4db73861b8381146_16_220]] is a cluster graph.
Determine, for each statement given in the subquestion, if it is true or false.
There exists a
[[IMAGE:4db73861b8381146_19_239]] algorithm for CLUSTER VERTEX DELETION.
True
False
A published solution is not available for this question yet.
Question 46 MCQ · 3.0 marks
**Marbles** is a solitaire game played on an undirected graph [[IMAGE:4db73861b8381146_19_240]] , where each vertex has zero or more
marbles. A single move in this game consists of removing two marbles from a vertex [[IMAGE:4db73861b8381146_19_241]] and adding
one marble to an arbitrary neighbor of [[IMAGE:4db73861b8381146_19_242]] . Note that the vertex [[IMAGE:4db73861b8381146_19_243]] must have at least two marbles
on it before the move.
The **Marbles Elimination** problem asks: given a graph [[IMAGE:4db73861b8381146_19_244]] and a marble count [[IMAGE:4db73861b8381146_19_245]] for
each vertex [[IMAGE:4db73861b8381146_19_246]] , is there a sequence of valid moves that removes all but one marble?
**Example.** Consider a triangle graph with vertices [[IMAGE:4db73861b8381146_19_247]] and edges [[IMAGE:4db73861b8381146_19_248]] . If
we start with marbles [[IMAGE:4db73861b8381146_19_249]] , [[IMAGE:4db73861b8381146_19_250]] , [[IMAGE:4db73861b8381146_19_251]] (total [[IMAGE:4db73861b8381146_19_252]] ):
1. Move from [[IMAGE:4db73861b8381146_19_253]] to [[IMAGE:4db73861b8381146_19_254]] : now [[IMAGE:4db73861b8381146_19_255]] , [[IMAGE:4db73861b8381146_19_256]] , [[IMAGE:4db73861b8381146_19_257]] .
2. Move from [[IMAGE:4db73861b8381146_19_258]] to [[IMAGE:4db73861b8381146_19_259]] : now [[IMAGE:4db73861b8381146_19_260]] , [[IMAGE:4db73861b8381146_19_261]] , [[IMAGE:4db73861b8381146_19_262]] .
3. Move from [[IMAGE:4db73861b8381146_19_263]] to [[IMAGE:4db73861b8381146_19_264]] : now [[IMAGE:4db73861b8381146_19_265]] , [[IMAGE:4db73861b8381146_19_266]] , [[IMAGE:4db73861b8381146_19_267]] .
We end with exactly [[IMAGE:4db73861b8381146_19_268]] marble.
Based on the above data, answer the given subquestions.
Consider a path graph
[[IMAGE:4db73861b8381146_20_269]] with vertices [[IMAGE:4db73861b8381146_20_270]] (edges [[IMAGE:4db73861b8381146_20_271]] ). Starting configuration:
[[IMAGE:4db73861b8381146_20_272]] (total [[IMAGE:4db73861b8381146_20_273]] marbles). Can the game be won (reduced to exactly [[IMAGE:4db73861b8381146_20_274]]
marble)?
Yes
No
A published solution is not available for this question yet.
Question 47 MCQ · 3.0 marks
**Marbles** is a solitaire game played on an undirected graph [[IMAGE:4db73861b8381146_19_240]] , where each vertex has zero or more
marbles. A single move in this game consists of removing two marbles from a vertex [[IMAGE:4db73861b8381146_19_241]] and adding
one marble to an arbitrary neighbor of [[IMAGE:4db73861b8381146_19_242]] . Note that the vertex [[IMAGE:4db73861b8381146_19_243]] must have at least two marbles
on it before the move.
The **Marbles Elimination** problem asks: given a graph [[IMAGE:4db73861b8381146_19_244]] and a marble count [[IMAGE:4db73861b8381146_19_245]] for
each vertex [[IMAGE:4db73861b8381146_19_246]] , is there a sequence of valid moves that removes all but one marble?
**Example.** Consider a triangle graph with vertices [[IMAGE:4db73861b8381146_19_247]] and edges [[IMAGE:4db73861b8381146_19_248]] . If
we start with marbles [[IMAGE:4db73861b8381146_19_249]] , [[IMAGE:4db73861b8381146_19_250]] , [[IMAGE:4db73861b8381146_19_251]] (total [[IMAGE:4db73861b8381146_19_252]] ):
1. Move from [[IMAGE:4db73861b8381146_19_253]] to [[IMAGE:4db73861b8381146_19_254]] : now [[IMAGE:4db73861b8381146_19_255]] , [[IMAGE:4db73861b8381146_19_256]] , [[IMAGE:4db73861b8381146_19_257]] .
2. Move from [[IMAGE:4db73861b8381146_19_258]] to [[IMAGE:4db73861b8381146_19_259]] : now [[IMAGE:4db73861b8381146_19_260]] , [[IMAGE:4db73861b8381146_19_261]] , [[IMAGE:4db73861b8381146_19_262]] .
3. Move from [[IMAGE:4db73861b8381146_19_263]] to [[IMAGE:4db73861b8381146_19_264]] : now [[IMAGE:4db73861b8381146_19_265]] , [[IMAGE:4db73861b8381146_19_266]] , [[IMAGE:4db73861b8381146_19_267]] .
We end with exactly [[IMAGE:4db73861b8381146_19_268]] marble.
Based on the above data, answer the given subquestions.
Consider a cycle graph [[IMAGE:4db73861b8381146_20_275]] with vertices [[IMAGE:4db73861b8381146_20_276]] (edges
[[IMAGE:4db73861b8381146_20_277]] ). Starting configuration: [[IMAGE:4db73861b8381146_20_278]] (total
[[IMAGE:4db73861b8381146_20_279]] marbles). Can the game be won (reduced to exactly [[IMAGE:4db73861b8381146_20_280]] marble)?
Yes
No
A published solution is not available for this question yet.
Question 48 MCQ · 3.0 marks
**Marbles** is a solitaire game played on an undirected graph [[IMAGE:4db73861b8381146_19_240]] , where each vertex has zero or more
marbles. A single move in this game consists of removing two marbles from a vertex [[IMAGE:4db73861b8381146_19_241]] and adding
one marble to an arbitrary neighbor of [[IMAGE:4db73861b8381146_19_242]] . Note that the vertex [[IMAGE:4db73861b8381146_19_243]] must have at least two marbles
on it before the move.
The **Marbles Elimination** problem asks: given a graph [[IMAGE:4db73861b8381146_19_244]] and a marble count [[IMAGE:4db73861b8381146_19_245]] for
each vertex [[IMAGE:4db73861b8381146_19_246]] , is there a sequence of valid moves that removes all but one marble?
**Example.** Consider a triangle graph with vertices [[IMAGE:4db73861b8381146_19_247]] and edges [[IMAGE:4db73861b8381146_19_248]] . If
we start with marbles [[IMAGE:4db73861b8381146_19_249]] , [[IMAGE:4db73861b8381146_19_250]] , [[IMAGE:4db73861b8381146_19_251]] (total [[IMAGE:4db73861b8381146_19_252]] ):
1. Move from [[IMAGE:4db73861b8381146_19_253]] to [[IMAGE:4db73861b8381146_19_254]] : now [[IMAGE:4db73861b8381146_19_255]] , [[IMAGE:4db73861b8381146_19_256]] , [[IMAGE:4db73861b8381146_19_257]] .
2. Move from [[IMAGE:4db73861b8381146_19_258]] to [[IMAGE:4db73861b8381146_19_259]] : now [[IMAGE:4db73861b8381146_19_260]] , [[IMAGE:4db73861b8381146_19_261]] , [[IMAGE:4db73861b8381146_19_262]] .
3. Move from [[IMAGE:4db73861b8381146_19_263]] to [[IMAGE:4db73861b8381146_19_264]] : now [[IMAGE:4db73861b8381146_19_265]] , [[IMAGE:4db73861b8381146_19_266]] , [[IMAGE:4db73861b8381146_19_267]] .
We end with exactly [[IMAGE:4db73861b8381146_19_268]] marble.
Based on the above data, answer the given subquestions.
Consider the general **Marbles Elimination** decision problem with the following setup:
• Input: A graph [[IMAGE:4db73861b8381146_20_281]] with [[IMAGE:4db73861b8381146_20_282]] vertices, where one designated vertex [[IMAGE:4db73861b8381146_20_283]] has [[IMAGE:4db73861b8381146_20_284]] marbles and all other
vertices have [[IMAGE:4db73861b8381146_20_285]] marble each.
• Output: TRUE if we can reduce to exactly [[IMAGE:4db73861b8381146_20_286]] marble, FALSE otherwise.
What is the complexity of this problem?
The problem is solvable in polynomial time.
The problem is NP-complete.
The problem is in P but not known to be NP-complete.
The problem is not in NP.
A published solution is not available for this question yet.