Advanced Algorithms · End Term · 31 Aug 2025 · May 2025 term · Set QDB3

Question 10: Consider the following instance of Set Cover problem: Un…

Question 10

+3 marksOne correct option

Consider the following instance of Set Cover problem:

Universe $\mathcal{U} = \{a, b, c\}$
Family $\mathcal{F} = \{S_1 = \{a, b\}, S_2 = \{a\}, S_3 = \{b\}, S_4 = \{c\}\}$

We build the following DP table for finding the Minimum Set Cover.

$\Pi(X, j)$ : minimum number of sets from $S_1, \ldots, S_j$ required to cover $X$

$j$ / $X$	$\{a\}$	$\{b\}$	$\{c\}$	$\{a, b\}$	$\{a, c\}$	$\{b, c\}$	$\{a, b, c\}$
0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
1	1	1	$\infty$	1	$\infty$	$\infty$	$\infty$
2	1	1	$\infty$	1	$\infty$	$\infty$	$\infty$
3	1	1	$\infty$	1	$\infty$	$\infty$	$\infty$
4	1	1	1	1	2	2	?

What is the missing entry?

Show answer

Correct answer

See the whole paper Take it as a mock test

Question 10 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 31 Aug 2025, in the May 2025 term (IIT M IMPROVEMENT FN EXAM QIA1 31 Aug 2025). It carries 3 marks.

This question was also asked in

Advanced Algorithms End Term — 31 Aug 2025, Set QIA1 · question 10

Question 10: Consider the following instance of Set Cover problem: Un…

Question 10

This question was also asked in

More questions from this paper