Quiz Space

Advanced Algorithms · Quiz 1 · 16 Jul 2023 · May 2023 term

Question 10: Consider the following instance of the stable matching p…

Question 10

+3 marksOne correct option

Consider the following instance of the stable matching problem. Suppose there are 3 women (A, B, C) and 3 men (X, Y, Z), and their preferences as given below and answer the subquestions:

Men123
XABC
YBAC
ZABC
Women123
AYXZ
BXYZ
CXYZ

Consider the following matching: M = (X-C), (Y-B), (Z-A). Which of the following forms a blocking pair in the matching above?

  1. A

    (Y-A)

  2. B

    (X-B)

  3. C

    (Y-C)

  4. D

    (Z-B)

Show answer

Correct answer

  • B

    (X-B)

See the whole paperTake it as a mock test

Question 10 of 16 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 16 Jul 2023, in the May 2023 term (IIT M DEGREE AN2 EXAM QPE2 16 JULY 2023). It carries 3 marks.

More questions from this paper

  1. Q1Figure question
  2. Q2A circuit in a matroid is a minimal dependent set. In other words, a subset S of the universe U is a circuit if S is no…
  3. Q3Consider the following set system:\ ● The universe is the set of edges of a graph G\ ● A subset S of U is an independen…
  4. Q4Suppose there are M mice out on a field and there are H holes scattered across the ground that the mice can hide in. Ea…
  5. Q5Let L be an array of n integers. Our array indices start from 0.\ Let maxSum[i] denote the largest contiguous sum possi…
  6. Q6Recall the task scheduling problem: suppose you have n tasks to complete in n days; each task requires your attention f…
  7. Q7We have a set of jobs to be performed, and we are given the following information about each job: a job ID, the duratio…
  8. Q8Consider the following tree: What is the size of the maximum-size independent set for this tree?
  9. Q9Consider the following instance of the stable matching problem. Suppose there are 3 women (A, B, C) and 3 men (X, Y, Z)…
  10. Q11What is the value of f(6)?
  11. Q12Which of the following is a valid recurrence for f(n)?
  12. Q13You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …
  13. Q14You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …
  14. Q15You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …
  15. Q16You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want …