Question 108 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
True
False
A published solution is not available for this question yet.
Advanced Algorithms · Quiz 1 · May 2025
Advanced Algorithms · Quiz 1 · May 2025
← 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.
0 / 26 published solutions
Question 109 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
True
False
A published solution is not available for this question yet.
Question 110 MCQ · 3.0 marks
Based on the above data, answer the given subquestions.
True
False
A published solution is not available for this question yet.
Question 111 MCQ · 2.0 marks
Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane,
how big is the largest subset of these rectangles that contain a common point?
For each statement given in the subquestions, determine if it is true or false.
There is a polynomial-time reduction from BoxDepth to MaxClique.
True
False
A published solution is not available for this question yet.
Question 112 MCQ · 2.0 marks
Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane,
how big is the largest subset of these rectangles that contain a common point?
For each statement given in the subquestions, determine if it is true or false.
There is a polynomial-time algorithm for BoxDepth.
True
False
A published solution is not available for this question yet.
Question 113 MCQ · 2.0 marks
Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane,
how big is the largest subset of these rectangles that contain a common point?
For each statement given in the subquestions, determine if it is true or false.
Only one of the statements in the previous question can be true assuming **P** ≠ **NP**.
True
False
A published solution is not available for this question yet.
Question 114 MCQ · 2.0 marks
Suppose your friend comes up with an algorithm to solve Partition in time O(nM), where n is the
size of the input set and M is the sum of the absolute values of its elements. Which of the following
statements is correct?
Such an algorithm cannot be possibly correct, since it runs in polynomial time
and Partition is NP-hard.
Even if such an algorithm exists, then it does not imply that P=NP.
A published solution is not available for this question yet.
Question 115 MCQ · 2.0 marks
The problem AllOrNothing3Sat asks, given a 3CNF boolean formula, whether there is an
assignment to the variables such that each clause either has three True literals or has three False
literals.
Consider the following statements:
(1) There is a polynomial-time algorithm to solve AllOrNothing3Sat.
(2) There is a polynomial-time reduction from 3SAT to AllOrNothing3Sat.
Assuming P ≠ NP, which of the following is true?
Both statements are true.
Statement (1) is true and statement (2) is false.
Statement (1) is false and statement (2) is true.
Both statements are false.
A published solution is not available for this question yet.
Question 116 MSQ · 4.0 marks
Which of the following statements is true about a flow network?
Increasing the capacity of one edge (u,v) by 1 can result in an increase of at
most 1 in the max flow.
Increasing the capacity of one edge (u,v) by 1 will result in an increase of at
least 1 in the max flow.
Decreasing the capacity of one edge (u,v) by 1 can result in a decrease of at
most 1 in the max flow.
Decreasing the capacity of one edge (u,v) by 1 will result in a decrease of at
least 1 in the max flow.
A published solution is not available for this question yet.
Question 117 MCQ · 4.0 marks
Given a flow network (G, s, t, c) and a flow f, how will you determine if f is maximum flow?
If there is any edge that is not saturated to full capacity, then we can conclude
that f is not a maximum flow.
If the residual graph does not have any augmenting paths then f is a
maximum flow.
If the value of the flow f is not the sum of the capacities of the edges coming
out of the source s then f is not a maximum flow.
If the value of the flow f is not the sum of the capacities of the edges coming
into the sink t then f is not a maximum flow.
A published solution is not available for this question yet.
Question 118 MCQ · 2.0 marks
In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of
three columns and four rows, they are obtained by placing a point in each ofthe four possible
positions (accounting for symmetries), and then a circle in each of the other possible positions.
Some example cards are shown below.
Based on the above data, answer the given subquestions.
SWISH-SPECIAL is in P.
True
False
A published solution is not available for this question yet.
Question 119 MCQ · 2.0 marks
In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of
three columns and four rows, they are obtained by placing a point in each ofthe four possible
positions (accounting for symmetries), and then a circle in each of the other possible positions.
Some example cards are shown below.
Based on the above data, answer the given subquestions.
SWISH-SPECIAL is in NP.
True
False
A published solution is not available for this question yet.
Question 120 MCQ · 2.0 marks
In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of
three columns and four rows, they are obtained by placing a point in each ofthe four possible
positions (accounting for symmetries), and then a circle in each of the other possible positions.
Some example cards are shown below.
Based on the above data, answer the given subquestions.
SWISH-SPECIAL is NP-hard.
True
False
A published solution is not available for this question yet.
Question 121 MCQ · 2.0 marks
In this question, we consider a card game called SWISH.
In the commercial version of SWISH, there are 60 transparent cards. Those cards are made up of
three columns and four rows, they are obtained by placing a point in each ofthe four possible
positions (accounting for symmetries), and then a circle in each of the other possible positions.
Some example cards are shown below.
Based on the above data, answer the given subquestions.
SWISH-SPECIAL is NP-complete.
True
False
A published solution is not available for this question yet.
Question 122 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
Yes
No
A published solution is not available for this question yet.
Question 123 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
None
One
Three
All
A published solution is not available for this question yet.
Question 124 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
None
One
Three
All
A published solution is not available for this question yet.
Question 125 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
0
1/5
4/5
1
A published solution is not available for this question yet.
Question 126 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
0
1/3
2/3
1
A published solution is not available for this question yet.
Question 127 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
25
60
90
120
A published solution is not available for this question yet.
Question 128 MCQ · 1.0 marks
Based on the above data, answer the given subquestions.
25
50
90
100
A published solution is not available for this question yet.
Question 129 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Question 130 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
Further, if the good event occurs, then:
A published solution is not available for this question yet.
Question 131 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Question 132 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Question 133 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
We continue the notation from the previous question. Suppose the randomly assigned weights
lead to the good event, that is, there is an unique perfect matching in G with minimum weight, and
say this minimum weight is r. What can you say about the determinant of Z in this case?
**LLM**
**Section Id :** 64065391701
**Section Number :** 8
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 16
**Number of Questions to be attempted :** 16
**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 :**
**Section Maximum Duration :** 0
**Section Minimum Duration :** 0
**Section Time In :** Minutes
A published solution is not available for this question yet.