Quiz Space

Advanced Algorithms · End Term · 3 Sept 2023 · May 2023 term · Set QPE1-S2

Question 5: Raj and Lata both designed an algorithm for the same mini…

Question 5

+3 marksOne correct option

Raj and Lata both designed an algorithm for the same minimization problem.

Raj proved that his algorithm Alg1Alg1 is a 2-approximation algorithm.
Lata proved that her algorithm Alg2Alg2 is a 4-approximation algorithm.

Is the following statement true or false?

There must be an input II such that Alg1(I)<Alg2(I)Alg1(I) < Alg2(I).

Recall that to say that a problem has a cc-approximation algorithm for some constant cc means that the output of the algorithm is always at most c⋅OPT(I)c \cdot OPT(I) on all inputs II.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

See the whole paperTake it as a mock test

Question 5 of 34 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 3 Sept 2023, in the May 2023 term (IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep). It carries 3 marks.

More questions from this paper

  1. Q1Recall the Dance Class problem: Problem Definition Dance Classes Input: A collection of n intervals given by their left…
  2. Q2Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible…
  3. Q3True or false?\ It is possible that Independent-Set is in P and the problem of checking a graph has a Hamiltonian Path …
  4. Q4Figure question
  5. Q6Recall 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…
  6. Q7Figure question
  7. Q8Recall the Dance Class problem: Problem Definition Dance Classes Input: A collection of n intervals given by their left…
  8. Q9Recall the Stable Matching problem: Stable Matching Input: Two sets given by M = {m_1, \ldots, m_n} (the men) and W = {…
  9. Q10Is the collection of outgoing 1/2-factors over the set A a matroid?
  10. Q11Is the collection of incoming 1/2-factors over the set A a matroid?
  11. Q12Is the collection of 1-factors over the set A a matroid?
  12. Q13Can the collection of 1-factors be defined as the intersection of two matroids?
  13. Q14Based on the above data, answer the given subquestions.
  14. Q15The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  15. Q16The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  16. Q17The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  17. Q18The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  18. Q19The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  19. Q20Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity acro…
  20. Q21You are supposed to start at the top of a number triangle and chose your passage all the way down by selecting between …
  21. Q22Consider the following orientation problem. We are given an undirected graph G = (V, E) and integer values p(v) for eve…
  22. Q23Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity acro…
  23. Q24Consider the partially carefully properly 5-colored graph below. What color should we give the vertex in the center to …
  24. Q25Based on the above data, answer the given subquestions.
  25. Q26In the Uncapacitated Facility Location (UCFL) problem, we are given (\mathcal{F} \uplus \mathcal{D}, d) as well auxilia…
  26. Q27Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  27. Q28Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  28. Q29Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  29. Q30Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  30. Q31Based on the above data, answer the given subquestions.
  31. Q32Based on the above data, answer the given subquestions.
  32. Q33Based on the above data, answer the given subquestions.
  33. Q34Recall the Traveling Salesman Problem: Definition Traveling Salesman Problem Input: A set of distinct cities {c_1, c_2,…