MauryaHub PYQ Practice

cs4021_2025T2_Q1_NA.pdf

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.

Question 108 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_2_0]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_2_1]]
Source diagram or notationSource diagram or notation
  1. True
  2. False

A published solution is not available for this question yet.

Question 109 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_2_0]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_2_2]]
Source diagram or notationSource diagram or notation
  1. True
  2. False

A published solution is not available for this question yet.

Question 110 MCQ · 3.0 marks

[[IMAGE:b16c1a4e7701f5aa_2_0]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_2_3]]
Source diagram or notationSource diagram or notation
  1. True
  2. 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.
  1. True
  2. 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.
  1. True
  2. 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**.
  1. True
  2. 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?
  1. Such an algorithm cannot be possibly correct, since it runs in polynomial time and Partition is NP-hard.
  2. 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?
  1. Both statements are true.
  2. Statement (1) is true and statement (2) is false.
  3. Statement (1) is false and statement (2) is true.
  4. 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?
  1. Increasing the capacity of one edge (u,v) by 1 can result in an increase of at most 1 in the max flow.
  2. Increasing the capacity of one edge (u,v) by 1 will result in an increase of at least 1 in the max flow.
  3. Decreasing the capacity of one edge (u,v) by 1 can result in a decrease of at most 1 in the max flow.
  4. 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?
  1. If there is any edge that is not saturated to full capacity, then we can conclude that f is not a maximum flow.
  2. If the residual graph does not have any augmenting paths then f is a maximum flow.
  3. 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.
  4. 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. [[IMAGE:b16c1a4e7701f5aa_6_4]] [[IMAGE:b16c1a4e7701f5aa_7_5]] Based on the above data, answer the given subquestions.
SWISH-SPECIAL is in P.
Source diagram or notationSource diagram or notation
  1. True
  2. 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. [[IMAGE:b16c1a4e7701f5aa_6_4]] [[IMAGE:b16c1a4e7701f5aa_7_5]] Based on the above data, answer the given subquestions.
SWISH-SPECIAL is in NP.
Source diagram or notationSource diagram or notation
  1. True
  2. 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. [[IMAGE:b16c1a4e7701f5aa_6_4]] [[IMAGE:b16c1a4e7701f5aa_7_5]] Based on the above data, answer the given subquestions.
SWISH-SPECIAL is NP-hard.
Source diagram or notationSource diagram or notation
  1. True
  2. 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. [[IMAGE:b16c1a4e7701f5aa_6_4]] [[IMAGE:b16c1a4e7701f5aa_7_5]] Based on the above data, answer the given subquestions.
SWISH-SPECIAL is NP-complete.
Source diagram or notationSource diagram or notation
  1. True
  2. False

A published solution is not available for this question yet.

Question 122 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_9_7]]
Source diagram or notationSource diagram or notation
  1. Yes
  2. No

A published solution is not available for this question yet.

Question 123 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_10_8]]
Source diagram or notationSource diagram or notation
  1. None
  2. One
  3. Three
  4. All

A published solution is not available for this question yet.

Question 124 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_10_9]]
Source diagram or notationSource diagram or notation
  1. None
  2. One
  3. Three
  4. All

A published solution is not available for this question yet.

Question 125 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_10_10]]
Source diagram or notationSource diagram or notation
  1. 0
  2. 1/5
  3. 4/5
  4. 1

A published solution is not available for this question yet.

Question 126 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_11_11]]
Source diagram or notationSource diagram or notation
  1. 0
  2. 1/3
  3. 2/3
  4. 1

A published solution is not available for this question yet.

Question 127 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_11_12]]
Source diagram or notationSource diagram or notation
  1. 25
  2. 60
  3. 90
  4. 120

A published solution is not available for this question yet.

Question 128 MCQ · 1.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_11_13]]
Source diagram or notationSource diagram or notation
  1. 25
  2. 50
  3. 90
  4. 100

A published solution is not available for this question yet.

Question 129 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_12_14]]
Source diagram or notationSource diagram or notation
  1. [[IMAGE:b16c1a4e7701f5aa_12_15]]
    Source diagram or notation
  2. [[IMAGE:b16c1a4e7701f5aa_12_16]]
    Source diagram or notation
  3. [[IMAGE:b16c1a4e7701f5aa_12_17]]
    Source diagram or notation
  4. [[IMAGE:b16c1a4e7701f5aa_12_18]]
    Source diagram or notation

A published solution is not available for this question yet.

Question 130 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
Further, if the good event occurs, then:
Source diagram or notation
  1. [[IMAGE:b16c1a4e7701f5aa_12_19]]
    Source diagram or notation
  2. [[IMAGE:b16c1a4e7701f5aa_12_20]]
    Source diagram or notation
  3. [[IMAGE:b16c1a4e7701f5aa_12_21]]
    Source diagram or notation
  4. [[IMAGE:b16c1a4e7701f5aa_13_22]]
    Source diagram or notation

A published solution is not available for this question yet.

Question 131 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_13_23]]
Source diagram or notationSource diagram or notation
  1. [[IMAGE:b16c1a4e7701f5aa_13_24]]
    Source diagram or notation
  2. [[IMAGE:b16c1a4e7701f5aa_13_25]]
    Source diagram or notation
  3. [[IMAGE:b16c1a4e7701f5aa_13_26]]
    Source diagram or notation
  4. [[IMAGE:b16c1a4e7701f5aa_13_27]]
    Source diagram or notation
  5. [[IMAGE:b16c1a4e7701f5aa_13_28]]
    Source diagram or notation
  6. [[IMAGE:b16c1a4e7701f5aa_13_29]]
    Source diagram or notation

A published solution is not available for this question yet.

Question 132 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] Based on the above data, answer the given subquestions.
[[IMAGE:b16c1a4e7701f5aa_13_30]]
Source diagram or notationSource diagram or notation
  1. [[IMAGE:b16c1a4e7701f5aa_13_31]]
    Source diagram or notation
  2. [[IMAGE:b16c1a4e7701f5aa_14_32]]
    Source diagram or notation
  3. [[IMAGE:b16c1a4e7701f5aa_14_33]]
    Source diagram or notation
  4. [[IMAGE:b16c1a4e7701f5aa_14_34]]
    Source diagram or notation

A published solution is not available for this question yet.

Question 133 MCQ · 2.0 marks

[[IMAGE:b16c1a4e7701f5aa_9_6]] 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?
Source diagram or notation
  1. [[IMAGE:b16c1a4e7701f5aa_14_35]]
    Source diagram or notation
  2. [[IMAGE:b16c1a4e7701f5aa_14_36]]
    Source diagram or notation
  3. [[IMAGE:b16c1a4e7701f5aa_14_37]]
    Source diagram or notation
  4. [[IMAGE:b16c1a4e7701f5aa_14_38]]       **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
    Source diagram or notation

A published solution is not available for this question yet.