Consider the following instance of Set Cover problem: - Universe \mathcal{U} = {a, b, c, d} - Family \mathcal{F} = \left{S_1 = {a, c}, S_2 = {a, d}, S_3 = {b, d}, S_4 = {b, c}\right} We use dynamic programming to find the minimum number of sets from \mathcal{F} required to cover \mathcal{U}. Recall that for every X \subseteq \mathcal{U} and every 0 \leq j \leq |\mathcal{F}|, our algorithm computes and stores \Pi(X, j), i.e., minimum number of sets from \mathcal{F}_j = {S_1, \ldots, S_j} required to cover X. Consider the following DP table: | {a, b, c, d} | \infty | \infty | \infty | 2 | 2 | | --- | --- | --- | --- | --- | --- | | {b, c, d} | \infty | \infty | \infty | 2 | 2 | | {a, c, d} | \infty | \infty | 2 | 2 | 2 | | {a, b, d} | \infty | \infty | \infty | 2 | 2 | | {a, b, c} | \infty | \infty | \infty | 2 | 2 | | {c, d} | \infty | \infty | 2 | 2 | 2 | | {b, d} | \infty | \infty | \infty | 1 | 1 | | {b, c} | \infty | \infty | \infty | 2 | 1 | | {a, d} | \infty | \infty | 1 | 1 | 1 | | {a, c} | \infty | 1 | 1 | 1 | 1 | | {a, b} | \infty | \infty | \infty | 2 | 2 | | {d} | \infty | \infty | 1 | 1 | 1 | | {c} | \infty | 1 | 1 | 1 | 1 | | {b} | \infty | \infty | \infty | 1 | 1 | | {a} | \infty | 1 | 1 | 1 | 1 | | \Phi | 0 | 0 | 0 | 0 | 0 | | X / j | 0 | 1 | 2 | 3 | 4 | Based on the above data, answer the given subquestions. Which DP table entries do we lookup to find Π({a, c, d}, 3)?

(C) Option figure from the original question paper

(A) Option figure from the original question paper

(B) Option figure from the original question paper

(D) Option figure from the original question paper

Consider the following instance of Set Cover problem: - Universe \mathcal{U} = {a, b, c, d} - Family \mathcal{F} = \left{S_1 = {a, c}, S_2 = {a, d}, S_3 = {b, d}, S_4 = {b, c}\right} We use dynamic programming to find the minimum number of sets from \mathcal{F} required to cover \mathcal{U}. Recall that for every X \subseteq \mathcal{U} and every 0 \leq j \leq |\mathcal{F}|, our algorithm computes and stores \Pi(X, j), i.e., minimum number of sets from \mathcal{F}_j = {S_1, \ldots, S_j} required to cover X. Consider the following DP table: | {a, b, c, d} | \infty | \infty | \infty | 2 | 2 | | --- | --- | --- | --- | --- | --- | | {b, c, d} | \infty | \infty | \infty | 2 | 2 | | {a, c, d} | \infty | \infty | 2 | 2 | 2 | | {a, b, d} | \infty | \infty | \infty | 2 | 2 | | {a, b, c} | \infty | \infty | \infty | 2 | 2 | | {c, d} | \infty | \infty | 2 | 2 | 2 | | {b, d} | \infty | \infty | \infty | 1 | 1 | | {b, c} | \infty | \infty | \infty | 2 | 1 | | {a, d} | \infty | \infty | 1 | 1 | 1 | | {a, c} | \infty | 1 | 1 | 1 | 1 | | {a, b} | \infty | \infty | \infty | 2 | 2 | | {d} | \infty | \infty | 1 | 1 | 1 | | {c} | \infty | 1 | 1 | 1 | 1 | | {b} | \infty | \infty | \infty | 1 | 1 | | {a} | \infty | 1 | 1 | 1 | 1 | | \Phi | 0 | 0 | 0 | 0 | 0 | | X / j | 0 | 1 | 2 | 3 | 4 | Based on the above data, answer the given subquestions. Which DP table entries do we lookup to find Π({a, b, c}, 2)?

(D) Option figure from the original question paper

(A) Option figure from the original question paper

(B) Option figure from the original question paper

(C) Option figure from the original question paper

Advanced Algorithms End Term PYQ Sep 2023: 24 Dec 2023 (Set FDB1)

Question 1

+2 marksNumerical answer

In one term of an academic program, we have $n$ days. Students have to earn at least $P$ credits during these $n$ days to remain in the program. There are two ways to earn points — completing practical tasks and attending lessons. For each task, a student earns $T$ points, and for each lesson, a student earns $L$ points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day 1 (and can be completed on any day from 1 to $n$ ), the second task is unlocked on day 8 (and can be completed on any day from 8 to $n$ ), the third task is unlocked on day 15, and so on.

Every day from 1 to $n$ , there is a lesson which can be attended by the students of the program. And every day, students choose whether to study or to rest the whole day. When a student decides to study, he or she attends a lesson and can complete no more than 2 tasks, which are already unlocked and not completed yet. If a student rests the whole day, he skips a lesson and ignores tasks.

Students naturally wants to have as many days off as possible, i. e. they want to maximize the number of rest days. Let's calculate this maximum.

As an example: if $n = 100, P = 20, L = 1$ and $T = 10$ , then by studying only on day 42 we attend a lesson gives (1 point), and can solve 2 out of 6 available tasks to get another 20 points. This is necessary and sufficient, and leads to 99 rest days.

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 0

Question 1 on its own page

Question 2

+2 marksNumerical answer

In one term of an academic program, we have $n$ days. Students have to earn at least $P$ credits during these $n$ days to remain in the program. There are two ways to earn points — completing practical tasks and attending lessons. For each task, a student earns $T$ points, and for each lesson, a student earns $L$ points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day 1 (and can be completed on any day from 1 to $n$ ), the second task is unlocked on day 8 (and can be completed on any day from 8 to $n$ ), the third task is unlocked on day 15, and so on.

Every day from 1 to $n$ , there is a lesson which can be attended by the students of the program. And every day, students choose whether to study or to rest the whole day. When a student decides to study, he or she attends a lesson and can complete no more than 2 tasks, which are already unlocked and not completed yet. If a student rests the whole day, he skips a lesson and ignores tasks.

Students naturally wants to have as many days off as possible, i. e. they want to maximize the number of rest days. Let's calculate this maximum.

As an example: if $n = 100, P = 20, L = 1$ and $T = 10$ , then by studying only on day 42 we attend a lesson gives (1 point), and can solve 2 out of 6 available tasks to get another 20 points. This is necessary and sufficient, and leads to 99 rest days.

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 27

Question 2 on its own page

Question 3

+2 marksOne correct option

In one term of an academic program, we have $n$ days. Students have to earn at least $P$ credits during these $n$ days to remain in the program. There are two ways to earn points — completing practical tasks and attending lessons. For each task, a student earns $T$ points, and for each lesson, a student earns $L$ points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day 1 (and can be completed on any day from 1 to $n$ ), the second task is unlocked on day 8 (and can be completed on any day from 8 to $n$ ), the third task is unlocked on day 15, and so on.

Every day from 1 to $n$ , there is a lesson which can be attended by the students of the program. And every day, students choose whether to study or to rest the whole day. When a student decides to study, he or she attends a lesson and can complete no more than 2 tasks, which are already unlocked and not completed yet. If a student rests the whole day, he skips a lesson and ignores tasks.

Students naturally wants to have as many days off as possible, i. e. they want to maximize the number of rest days. Let's calculate this maximum.

As an example: if $n = 100, P = 20, L = 1$ and $T = 10$ , then by studying only on day 42 we attend a lesson gives (1 point), and can solve 2 out of 6 available tasks to get another 20 points. This is necessary and sufficient, and leads to 99 rest days.

Based on the above data, answer the given subquestions.

A
B
C
D

Show answer

Correct answer

D

Question 3 on its own page

Question 4

+2 marksOne correct option

In one term of an academic program, we have $n$ days. Students have to earn at least $P$ credits during these $n$ days to remain in the program. There are two ways to earn points — completing practical tasks and attending lessons. For each task, a student earns $T$ points, and for each lesson, a student earns $L$ points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day 1 (and can be completed on any day from 1 to $n$ ), the second task is unlocked on day 8 (and can be completed on any day from 8 to $n$ ), the third task is unlocked on day 15, and so on.

Every day from 1 to $n$ , there is a lesson which can be attended by the students of the program. And every day, students choose whether to study or to rest the whole day. When a student decides to study, he or she attends a lesson and can complete no more than 2 tasks, which are already unlocked and not completed yet. If a student rests the whole day, he skips a lesson and ignores tasks.

Students naturally wants to have as many days off as possible, i. e. they want to maximize the number of rest days. Let's calculate this maximum.

As an example: if $n = 100, P = 20, L = 1$ and $T = 10$ , then by studying only on day 42 we attend a lesson gives (1 point), and can solve 2 out of 6 available tasks to get another 20 points. This is necessary and sufficient, and leads to 99 rest days.

Based on the above data, answer the given subquestions.

A
the first q days of the term
B
the last q days of the term
C
the middle q days of the term
D
it makes no difference

Show answer

Correct answer

A
the first q days of the term

Question 4 on its own page

Question 5

+2 marksOne correct option

A
TRUE
B
FALSE

Show answer

Correct answer

A
TRUE

Question 5 on its own page

Question 6

+3 marksOne or more correct options

Choose the correct options

Select all that apply.

A
B
C

Show answer

Correct answers

A
C

Question 6 on its own page

Question 7

+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 \backslash 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?

A
0
B
1
C
2
D
3

Show answer

Correct answer

C
2

Question 7 on its own pageAlso asked in End Term 24 Dec 2023

Question 8

+2 marksOne correct option

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target.
Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other.
Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.
Based on the above data, answer the given subquestions.

What is the answer if $R = C = N$ and all the squares along a diagonal are cut out? In particular, assume the square at the intersection of the $i$ -th row (from the top) and the $i$ -th column (from the left) is a cut out square, for all $1 \leqslant i \leqslant N$ . For this question, assume that $N = 2K$ , i.e, that $N$ is even.

A
B
C
D

Show answer

Correct answer

C

Question 8 on its own page

Question 9

+2 marksOne correct option

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target.
Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other.
Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.
Based on the above data, answer the given subquestions.

What is the answer if R = C = N and all the squares on the topmost row and rightmost column (i.e, a L-shape) are cut out?

A
B
C
D

Show answer

Correct answer

D

Question 9 on its own page

Question 10

+2 marksOne correct option

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target.
Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other.
Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.
Based on the above data, answer the given subquestions.

Consider the following bipartite graph: the set A is composed of elements corresponding to every row of the board, while set B consists of the columns. For each row add edges to every column if the corresponding square is not cut out of the board. What does the answer correspond to in this graph?

A
the maximum vertex degree
B
the number of edges in a minimum spanning forest
C
the size of a maximum matching
D
none of these

Show answer

Correct answer

C
the size of a maximum matching

Question 10 on its own pageAlso asked in End Term 24 Dec 2023

Question 11

+2 marksOne correct option

You have been given a R × C chessboard, with a list of squares cut out. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target.
Find the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other.
Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.
Based on the above data, answer the given subquestions.

What is the number of valid placements of N mutually non-attacking rooks if R = C = N and there are no cut out squares? Two placements are distinct if there is at least one square which has a rook in one of them and does not have a rook in the other.

A
2N
B
2*^(N)*
C
N!
D
N²

Show answer

Correct answer

C
N!

Question 11 on its own page

Question 12

+3 marksOne correct option

Consider the following instance of Set Cover problem:

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

We use dynamic programming to find the minimum number of sets from $\mathcal{F}$ required to cover $\mathcal{U}$ . Recall that for every $X \subseteq \mathcal{U}$ and every $0 \leq j \leq |\mathcal{F}|$ , our algorithm computes and stores $\Pi(X, j)$ , i.e., minimum number of sets from $\mathcal{F}_j = \{S_1, \ldots, S_j\}$ required to cover $X$ .

Consider the following DP table:

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

Based on the above data, answer the given subquestions.

Which DP table entries do we lookup to find Π({a, c, d}, 3)?

A
B
C
D

Show answer

Correct answer

C

Question 12 on its own page

Question 13

+3 marksOne correct option

Consider the following instance of Set Cover problem:

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

We use dynamic programming to find the minimum number of sets from $\mathcal{F}$ required to cover $\mathcal{U}$ . Recall that for every $X \subseteq \mathcal{U}$ and every $0 \leq j \leq |\mathcal{F}|$ , our algorithm computes and stores $\Pi(X, j)$ , i.e., minimum number of sets from $\mathcal{F}_j = \{S_1, \ldots, S_j\}$ required to cover $X$ .

Consider the following DP table:

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

Based on the above data, answer the given subquestions.

Which DP table entries do we lookup to find Π({a, b, c}, 2)?

A
B
C
D

Show answer

Correct answer

D

Question 13 on its own page

Question 14

+1 markNumerical answer

The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalization of the popular Fibonacci numbers that you might expect):

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 5

Question 14 on its own page

Question 15

+1 markNumerical answer

The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalization of the popular Fibonacci numbers that you might expect):

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 11

Question 15 on its own page

Question 16

+1 markNumerical answer

The three-bonaci numbers are defined as follows (please read the definition carefully, as it may not be the generalization of the popular Fibonacci numbers that you might expect):

Based on the above data, answer the given subquestions.

Show answer

Correct answer: 500

Question 16 on its own page

Question 17

+3 marksOne correct option

In the MIN-2-SAT problem, we are given a 2-CNF formula $\phi$ and an integer $k$ , and the objective is to decide whether there exists an assignment for $\phi$ that satisfies at most $k$ clauses.

Consider the following branching algorithm for the problem.

If there is a variable $x$ that occurs only positively in $\phi$ , observe that there exists an optimal assignment that sets it to $0$ . Similarly, if there is a variable $x$ that occurs only positively in $\phi$ , there exists an optimal assignment that sets it to $1$ . Once we perform this preprocessing, assuming that have clauses remaining, we have the following guarantee:

Every variable has at least one positive and one negated occurrence.

Now we can branch exhaustively on the settings of variables. The overall algorithm is summarized in the following pseudocode:

text

1MINSAT(phi,k):
2    if there is a variable x that occurs only as a positive literal:
3        set x to 0
4    if there is a variable x that occurs only as a negated literal:
5        set x to 1
6
7    if phi is empty:
8        return YES
9    if phi is not empty and k <= 0:
10        return NO
11
12    Let x be any variable that occurs in phi.
13    return MINSAT(phi|[x = TRUE],k-1) OR MINSAT(phi|[x = FALSE],k-1)

What is the running time of this algorithm? Select the tightest bound that is correct according to you.

A
B
C
D

Show answer

Correct answer

C

Question 17 on its own page

Question 18

+2 marksOne correct option

Consider the given statements and answer if they are true or false.

The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.

A
TRUE
B
FALSE

Show answer

Correct answer

B
FALSE

Question 18 on its own pageAlso asked in End Term 24 Dec 2023, End Term 10 May 2026

Question 19

+2 marksOne correct option

Consider the given statements and answer if they are true or false.

A
TRUE
B
FALSE

Show answer

Correct answer

B
FALSE

Question 19 on its own page

Question 20

+2 marksOne correct option

Answer the given subquestions.

Every linear program has a unique optimal solution.

A
TRUE
B
FALSE

Show answer

Correct answer

B
FALSE

Question 20 on its own pageAlso asked in End Term 24 Dec 2023, End Term 31 Aug 2025, End Term 31 Aug 2025

Question 21

+2 marksOne correct option

Answer the given subquestions.

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$ , we have that $\{u, v\} \cap S$ is non-empty. Consider the algorithm that repeats the given steps as long as the graph has at least one edge avail able: select a vertex of maximum degree (say $w$ ), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$ .

Is it true that the algorithm always outputs a vertex cover?

A
Yes
B
No

Show answer

Correct answer

A
Yes

Question 21 on its own page

Question 22

+2 marksOne correct option

Answer the given subquestions.

Consider the algorithm in the previous question. Does the algorithm always output an optimal vertex cover?

A
Yes
B
No

Show answer

Correct answer

B
No

Question 22 on its own page

Question 23

+2 marksOne correct option

Answer the given subquestions.

Consider the algorithm in the previous question. Does the algorithm always output a 2- approximate vertex cover?

A
Yes
B
No

Show answer

Correct answer

B
No

Question 23 on its own page

Question 24

+2 marksOne correct option

Answer the given subquestions.

Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there examples of graphs where the size of the optimal vertex cover is exactly equal to twice the size of its maximum matching? For example, this is not true for a path on three vertices: the size of both the maximum matching and minimum vertex cover is 1.

A
Yes
B
No

Show answer

Correct answer

A
Yes

Question 24 on its own pageAlso asked in End Term 24 Dec 2023, End Term 31 Aug 2025, End Term 31 Aug 2025