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.

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

Advanced Algorithms End Term: 31 August 2025, Set QDB3 (May 2025 term)

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.

Also 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²

Question 3

+2 marksOne correct option

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

18 more questions in this paper

Sign in with Google — it is free — to see every question with its answer and explanation, practise it in learning mode, or take it as a timed mock test.

More on the Advanced Algorithms End Term 31 Aug 2025 Set QDB3 paper

The IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 31 Aug 2025, in the May 2025 term, set QDB3: 21 questions for 50 marks in 180 minutes. The first 3 questions are below. Sign in with Google — it is free — to see the whole paper with its answers and explanations, in learning mode or as a timed mock test.

Feature	Advanced Algorithms End Term 31 Aug 2025 Set QDB3 at a glance
Term	May 2025 term
Subject	Advanced Algorithms
Course code	BSCS4021
Questions	21
Marks	50
Duration	180 min
MCQ	18
Numerical	2
MSQ	1
Official paper	IIT M IMPROVEMENT FN EXAM QIA1 31 Aug 2025
Negative marking	No negative marking.
Updated	25 Sept 2026

Other sets that day

Set QIA1