Figure from the original question paper

(A) At each iteration, pick the remaining request with the fewest number of conflicts with other remaining requests (breaking ties arbitrarily).

(B) At each iteration, pick the remaining request with the earliest start time.

(C) At each iteration, pick the remaining request with the earliest finish time.

(D) At each iteration, pick the remaining request which requires the least time (i.e., has the smallest value of ti — si) (breaking ties arbitrarily).

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

(D) Option figure from the original question paper

(E) Option figure from the original question paper

(F) Option figure from the original question paper

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 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: 1 September 2024, Set QDB1 (May 2024 term)

Question 1

+2 marksOne correct option

A
At each iteration, pick the remaining request with the fewest number of conflicts with other remaining requests (breaking ties arbitrarily).
B
At each iteration, pick the remaining request with the earliest start time.
C
At each iteration, pick the remaining request with the earliest finish time.
D
At each iteration, pick the remaining request which requires the least time (i.e., has the smallest value of ti — si) (breaking ties arbitrarily).

Question 2

+2 marksOne correct option

Question 3

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

50 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 1 Sept 2024 Set QDB1 paper

The IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 1 Sept 2024, in the May 2024 term, set QDB1: 53 questions for 100 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 1 Sept 2024 Set QDB1 at a glance
Term	May 2024 term
Subject	Advanced Algorithms
Course code	BSCS4021
Questions	53
Marks	100
Duration	180 min
MCQ	42
Numerical	8
MSQ	3
Official paper	IIT M DEGREE AN EXAM QDB3 01 Sep 2024
Negative marking	No negative marking.
Updated	25 Sept 2026

Other sets that day

Set QDB3