Question 210 NAT · 3.0 marks
A published solution is not available for this question yet.
Advanced Algorithms · Quiz 2 · May 2023
Advanced Algorithms · Quiz 2 · May 2023
← Course papers · Start practice / exam
This page contains the reliably extracted subset, not the complete original paper.
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
0 / 15 published solutions
Question 211 NAT · 3.0 marks
A published solution is not available for this question yet.
Question 212 MCQ · 2.0 marks
Non-emptiness
Heredity
The Exchange Property
None of these
A published solution is not available for this question yet.
Question 213 MSQ · 2.0 marks
Non-emptiness
Heredity
The Exchange Property
None of these
A published solution is not available for this question yet.
Question 214 MCQ · 3.0 marks
Based on the above data, answer the given subquestions.
Which of the following is a valid recurrence for **dp[i]**?
A published solution is not available for this question yet.
Question 215 NAT · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Question 216 NAT · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Question 217 MSQ · 3.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Question 218 MCQ · 3.0 marks
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.
Statement 1
Statement 2
Both statements
Neither statement
A published solution is not available for this question yet.
Question 219 MCQ · 2.0 marks
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 220 MSQ · 5.0 marks
A published solution is not available for this question yet.
Question 221 MCQ · 5.0 marks
the size of a maximum independent set in G
the size of a maximum matching in G
the size of a minimum feedback vertex set in G
the size of a minimum odd cycle transversal G
A published solution is not available for this question yet.
Question 222 MCQ · 5.0 marks
Yes, because we can reduce 3SAT to NICE SET.
Yes, because we can reduce NICE SET to 3SAT.
No, because we can reduce NICE SET to MAX FLOW.
No, because we can reduce MAX FLOW to NICE SET.
A published solution is not available for this question yet.
Question 223 MCQ · 5.0 marks
No, because the problem can be solved in polynomial time.
Yes, because we can reduce 3SAT to ALL-or-NOTHING-3SAT.
Yes, because we can reduce ALL-or-NOTHING-3SAT to 3SAT.
A published solution is not available for this question yet.
Question 224 MCQ · 5.0 marks
This does not work, because we might report an invalid solution.
This gives a valid solution, but the approximation ratio becomes worse.
This gives a valid solution, and in fact the solution is always exactly the same as
in the original rounding scheme.
This gives a valid solution. We sometimes report a better solution than in the
original rounding scheme, but the approximation ratio of the algorithm is still more than 2 - ϵ for
any ϵ > 0.
This gives a valid solution, and the approximation ratio of the algorithm
becomes 3/2.
**Data Viz**
**Section Id :** 64065339869
**Section Number :** 13
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 4
**Number of Questions to be attempted :** 4
**Section Marks :** 100
**Display Number Panel :** Yes
**Group All Questions :** No
**Enable Mark as Answered Mark for Review and**
Yes
**Clear Response :**
**Maximum Instruction Time :** 0
A published solution is not available for this question yet.