In this problem you are given as input a graph T = (V, E) that is a tree (that is, T is undirected, connected, and acyclic). A perfect matching of T is a subset F \subset E of edges such that every vertex v \in V is the endpoint of exactly one edge of F. Equivalently, F matches each vertex of T with exactly one other vertex of T. For example, a path graph has a perfect matching if and only if it has an even number of vertices. Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it. Algorithm A: 1 While T has at least one vertex: 2 If T has no edges: 3 halt and output ”T has no perfect matching.” 4 Else: 5 Let v be a vertex of T with maximum degree. 6 Choose an arbitrary edge e incident to v. 7 Delete e and its two endpoints from T. 8 (end of while loop] 9 Halt and output ”T has a perfect matching.” Algorithm B: 1 While T has at least one vertex: 2 If T has no edges: 3 halt and output ”T has no perfect matching.” 4 Else: 5 Let v be a vertex of T with minimum non-zero degree. 6 Choose an arbitrary edge e incident to v. 7 Delete e and its two endpoints from T. 8 (end of while loop] 9 Halt and output ”T has a perfect matching.” Is either algorithm correct? Hint: Recall that every tree with at least two vertices has at least one degree one vertex.

(C) Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.

(A) Neither algorithm always correctly determines whether or not a given tree graph has a perfect matching.

(B) Both algorithms always correctly determine whether or not a given tree graph has a perfect matching.

(D) Algorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.

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. Figure from the original question paper

(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. Figure from the original question paper

(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

Figure from the original question paper

(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 May 2025: 31 Aug 2025 (Set QIA1)

Question 1

+3 marksOne correct option

In this problem you are given as input a graph $T = (V, E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A perfect matching of $T$ is a subset $F \subset E$ of edges such that every vertex $v \in V$ is the endpoint of exactly one edge of $F$ .

Equivalently, $F$ matches each vertex of $T$ with exactly one other vertex of $T$ . For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it.

Algorithm A:

text

11 While T has at least one vertex:
22   If T has no edges:
33       halt and output ”T has no perfect matching.”
44   Else:
55       Let v be a vertex of T with maximum degree.
66       Choose an arbitrary edge e incident to v.
77       Delete e and its two endpoints from T.
88 (end of while loop]
99 Halt and output ”T has a perfect matching.”

Algorithm B:

text

11 While T has at least one vertex:
22   If T has no edges:
33       halt and output ”T has no perfect matching.”
44   Else:
55       Let v be a vertex of T with minimum non-zero degree.
66       Choose an arbitrary edge e incident to v.
77       Delete e and its two endpoints from T.
88 (end of while loop]
99 Halt and output ”T has a perfect matching.”

Is either algorithm correct?

Hint: Recall that every tree with at least two vertices has at least one degree one vertex.

A
Neither algorithm always correctly determines whether or not a given tree graph has a perfect matching.
B
Both algorithms always correctly determine whether or not a given tree graph has a perfect matching.
C
Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.
D
Algorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.

Show answer

Correct answer

C
Algorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.

Question 1 on its own pageAlso asked in End Term 1 Sept 2024, End Term 31 Aug 2025

Question 2

+2 marksOne correct option

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$ , $1$ , and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

A
3ⁿ
B
2ⁿ
C
n³
D
n²

Show answer

Correct answer

B
2ⁿ

Question 2 on its own page

Question 3

+2 marksOne correct option

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$ , $1$ , and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

A
2ⁿ
B
n
C
1
D
0

Show answer

Correct answer

C
1

Question 3 on its own page

Question 4

+2 marksOne correct option

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$ , $1$ , and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

A
3ⁿ
B
2ⁿ
C
1
D
0

Show answer

Correct answer

D
0

Question 4 on its own page

Question 5

+2 marksNumerical answer

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$ , $1$ , and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

For n = 4, calculate the number of sequences of length 4 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Show answer

Correct answer: 36

Question 5 on its own pageAlso asked in Quiz 2 3 Aug 2025

Question 6

+2 marksNumerical answer

Consider the task of counting how many sequences of length $n$ exist consisting only of numbers $0$ , $1$ , and $2$ such that each number occurs at least once. We will solve this by calculating the number of sequences which do not contain at least one of the numbers.

Let's denote by $A_i$ $(i = 0, 1, 2)$ the set of sequences in which the digit $i$ does not occur. The formula of inclusion-exclusion on the number of "bad" sequences is given by:

$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$

Based on the above data, answer the given subquestions.

For n = 5, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Show answer

Correct answer: 150

Question 6 on its own pageAlso asked in Quiz 2 3 Aug 2025

Question 7

+3 marksOne or more correct options

Select all that apply.

A
It is in P.
B
It is in NP.
C
It is NP-hard.
D
It is NP-complete.

Show answer

Correct answers

A
It is in P.
B
It is in NP.

Question 7 on its own page

Question 8

+3 marksOne or more correct options

Choose the correct options:

Select all that apply.

A
B
C

Show answer

Correct answers

A
C

Question 8 on its own page

Question 9

+2 marksOne correct option

A
TRUE
B
FALSE

Show answer

Correct answer

A
TRUE

Question 9 on its own page

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?

A
0
B
1
C
2
D
3

Show answer

Correct answer

C
2

Question 10 on its own pageAlso asked in End Term 31 Aug 2025

Question 11

+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.

A
B
C
D

Show answer

Correct answer

C

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.

A
B
C
D

Show answer

Correct answer

D

Question 12 on its own page

Question 13

+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 exhuastively 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 13 on its own page

Question 14

+2 marksOne correct option

Consider the following statements and answer the given subquestions 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 14 on its own pageAlso asked in Quiz 2 4 Aug 2024

Question 15

+2 marksOne correct option

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

An adversary can provide randomized quicksort with an input array of length $n$ that forces the algorithm to run in $\omega(n \lg n)$ time on that input.

(If you are not familiar with the $\omega$ asymptotic notation, it roughly translates as “at least’ ’. For example, we can say that it is possible to come up with an input that forces insertion sort to run for $\omega(n^2)$ steps.)

A
TRUE
B
FALSE

Show answer

Correct answer

B
FALSE

Question 15 on its own pageAlso asked in Quiz 2 4 Aug 2024

Question 16

+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 16 on its own pageAlso asked in End Term 24 Dec 2023, End Term 24 Dec 2023, End Term 31 Aug 2025

Question 17

+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 following steps as long as the graph has at least one edge available: 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 17 on its own pageAlso asked in End Term 24 Dec 2023, End Term 31 Aug 2025

Question 18

+2 marksOne correct option

Answer the given subquestions.

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

A
Yes
B
No

Show answer

Correct answer

B
No

Question 18 on its own page

Question 19

+2 marksOne correct option

Answer the given subquestions.

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

A
Yes
B
No

Show answer

Correct answer

B
No

Question 19 on its own page

Question 20

+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 20 on its own pageAlso asked in End Term 24 Dec 2023, End Term 24 Dec 2023, End Term 31 Aug 2025

Question 21

+3 marksOne correct option

A
B
C
D

Show answer

Correct answer

D

Question 21 on its own page