Quiz Space

Advanced Algorithms · Quiz 1 · 29 Oct 2023 · September 2023 term

Question 2: Consider the following instance of the stable matching pr…

Question 2

+2 marksOne correct option

Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ).

P: W > X > Y > Z
Q: X > Y > Z > W
R: W > X > Z > Y
S: X > Y > W > Z

and

W: S > Q > R > P
X: P > S > Q > R
Y: R > P > Q > S
Z: R > P > S > Q

Consider the following matching: M = {(P, W), (Q, X), (R, Z), (S, Y)}.

Which of the following is a blocking pair in the matching above?

  1. A

    (P-X)

  2. B

    (Q-Y)

  3. C

    (R-W)

  4. D

    (S-X)

Show answer

Correct answer

  • D

    (S-X)

See the whole paperTake it as a mock test

Question 2 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 29 Oct 2023, in the September 2023 term (IIT M DEGREE AN2 EXAM QPE2 29 Oct 2023). It carries 2 marks.

More questions from this paper

  1. Q1Which of the following statements is true? Statement 1: For every graph G and every maximum flow on G, there always exi…
  2. Q3Consider 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}. Suppose we are…
  3. Q4Figure question
  4. Q5Figure question
  5. Q6Figure question
  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. Q9There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  9. Q10Consider the following process. At all times you have a single positive integer x, which is initially equal to 1 . In e…
  10. Q11Consider the following process. At all times you have a single positive integer x, which is initially equal to 1 . In e…
  11. Q12Consider the following process. At all times you have a single positive integer x, which is initially equal to 1 . In e…
  12. Q13A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  13. Q14A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  14. Q15A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  15. Q16A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  16. Q17A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  17. Q18A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  18. Q19A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  19. Q20A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  20. Q21A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …