Quiz Space

Advanced Algorithms · Quiz 2 · 6 Aug 2023 · May 2023 term

Question 1: For the following sets of timings of dance classes, figur…

Question 1

+3 marksNumerical answer

For the following sets of timings of dance classes, figure out what is the largest number of classes that you can attend in a conflict-free fashion:

The number of classes is N = 9. The timings of the classes are given by:

  1. [1 - 5]
  2. [6 - 10]
  3. [11- 15]
  4. [16 - 20]
  5. [2 - 8]
  6. [3 - 8]
  7. [2 - 7]
  8. [9 - 12]
  9. [13 - 17]
Show answer

Correct answer: 4

See the whole paperTake it as a mock test

Question 1 of 15 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 6 Aug 2023, in the May 2023 term (IIT M DEGREE AN3 EXAM QPE3 06 Aug 2023). It carries 3 marks.

More questions from this paper

  1. Q2Consider 4 sets as follows: W = {w_1, w_2, w_3}, X = {x_1, x_2}, Y = {y_1, y_2, y_3} and Z = {z_1, z_2}. Given capacity…
  2. Q3Let G be a simple, undirected, unweighted graph. We use V(G) to denote the vertex set of G and E(G) to denote the edge …
  3. Q4Let G be a simple, undirected, unweighted graph. We use V(G) to denote the vertex set of G and E(G) to denote the edge …
  4. Q5There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  5. Q6There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  6. Q7There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  7. Q8There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  8. Q9Which of the following statements is true?\ Statement 1: For every graph G and every maximum flow on G, there always ex…
  9. Q10Figure question
  10. Q11Figure question
  11. Q12Consider the following definitions: A vertex cover is a subset S of V(G) such that for all (u,v) \in E(G), S \cap {u,v}…
  12. Q13Figure question
  13. Q14Figure question
  14. Q15Consider a different rounding strategy for the LP relaxation of the vertex cover problem. Instead of rounding up every …