Quiz Space

Advanced Algorithms · Quiz 2 · 4 Aug 2024 · May 2024 term

Advanced Algorithms Quiz 2 4 Aug 2024 — Question 3

Question 3

+3 marksOne correct option
  1. A

    Finding a Hamiltonian cycle in a graph is as hard as determining the answer to the Marbles Elimination question; i.e, there is a reduction from the problem of Marbles Elimination to the problem of finding a Hamiltonian cycle.

  2. B

    Determining the answer to the Marbles Elimination question is as hard as finding a Hamiltonian cycle in a graph; i.e, there is a reduction from the Hamiltonian cycle problem to the problem of Marbles Elimination.

  3. C

    Marbles Elimination is in P by a reduction to the Max Flow problem.

Show answer

Correct answer

  • B

    Determining the answer to the Marbles Elimination question is as hard as finding a Hamiltonian cycle in a graph; i.e, there is a reduction from the Hamiltonian cycle problem to the problem of Marbles Elimination.

See the whole paperTake it as a mock test

Question 3 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 4 Aug 2024, in the May 2024 term (IIT M DEGREE AN EXAM QDB2 4 Aug 2024). It carries 3 marks.

More questions from this paper

  1. Q1Consider the following graph. A triangle-free subset of seven vertices is highlighted. Find the size of the largest tri…
  2. Q2The TRIANGLE-FREEDOM problem is the following: the input is a simple undirected graph G and a positive integer k. An in…
  3. Q4Recall the max-flow problem: for a directed graph G(V, E) with non-negative capacities c_e for every e \in E and two sp…
  4. Q5Figure question
  5. Q6The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.
  6. Q7An adversary can provide randomized quicksort with an input array of length n that forces the algorithm to run in \omeg…
  7. Q8Figure question
  8. Q9Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  9. Q10Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  10. Q11Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  11. Q12Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  12. Q13Based on the above data, answer the given subquestions.
  13. Q14Based on the above data, answer the given subquestions.
  14. Q15Based on the above data, answer the given subquestions.
  15. Q16The construction described here is a valid reduction from 3-SAT to 3-Coloring.
  16. Q17The construction described here is a valid reduction from 3-Coloring to 3-SAT.
  17. Q18Argue that to solve SCS, it is sufficient to find:
  18. Q19Observe that for a given \pi, the length of the corresponding superstring s(\pi), which is obtained by writing the inpu…
  19. Q20We define an overlap graph OG(\mathcal{S}) associated with \mathcal{S} as follows: OG(\mathcal{S}) is a complete direct…
  20. Q21Does the greedy algorithm always produce the right answer?