Quiz Space

Advanced Algorithms · End Term · 1 Sept 2024 · May 2024 term · Set QDB1

Question 3: In this problem you are given as input a graph T = (V, E)…

Question 3

+3 marksOne correct option

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

Equivalently, FF matches each vertex of TT with exactly one other vertex of TT. 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
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:

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

  1. A

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

  2. B

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

  3. C

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

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

See the whole paperTake it as a mock test

Question 3 of 53 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 1 Sept 2024, in the May 2024 term (IIT M DEGREE AN EXAM QDB3 01 Sep 2024). It carries 3 marks.

More questions from this paper

  1. Q1Figure question
  2. Q2Figure question
  3. Q4Which of the following statements is true?\ Statement 1: For every graph G and every maximum flow on G, there always ex…
  4. Q5Recall the max-flow problem: for a directed graph G(V, E) with non-negative capacities c_e for every e \in E and two sp…
  5. Q6Figure question
  6. Q7A subset S of vertices in an undirected graph G is half-independent if each vertex in S is adjacent to at most one othe…
  7. Q8Can the disk with dimensions [2,1,2] be placed above [3,2,3]?
  8. Q9Can the disk with dimensions [2,2,2] be placed above [3,2,3]?
  9. Q10Suppose the input consists of the following triplets: [[3, 5, 7], [3, 2, 2], [3, 1, 1], [5, 5, 9]]. What’s the answer?
  10. Q11Our approach will be to building a DP table of the same length as the array of disks. Let d_i denote the i^{th} disk in…
  11. Q12With the same notation as in the previous question, consider the following alternate approach. We process the DP array …
  12. Q13With the same notation as in the previous questions, consider the following alternate approach. We first organize the d…
  13. Q14What is the complexity of this algorithm?
  14. Q15If we have 1 die with 6 sides, how many ways can we achieve a target sum of 4?
  15. Q16If we have 3 dice with 17 sides each, how many ways can we achieve a target sum of 7?
  16. Q17Suppose the input consists of 3 dice, each with 4 sides, and the target sum is 9. What’s the answer?
  17. Q18In which of the following scenarios will the answer be zero?
  18. Q19If we have one die with six sides, what are the achievable targets?
  19. Q20Let DP[N,T ] denote the number of ways to achieve a target sum of T > 0 using N > 0 dice. Which of the following recurs…
  20. Q21What is the value of DP[0, 0]?
  21. Q22What is the value of DP[0, T ] for any T > 0?
  22. Q23What is the value of DP[N , 0] for any N > 0?
  23. Q24What is the value of DP[N , T ] if T \< N ?
  24. Q25What is the complexity of this algorithm ?
  25. Q26Based on the above data, answer the given subquestions.
  26. Q27Based on the above data, answer the given subquestions.
  27. Q28Based on the above data, answer the given subquestions.
  28. Q29In this given subquestion, we will examine the relationship of treewidth with other graph parameters. Let G be an undir…
  29. Q30In this given subquestion, we will examine the relationship of treewidth with other graph parameters. Let G be an undir…
  30. Q31In this given subquestion, we will examine the relationship of treewidth with other graph parameters.
  31. Q32If the ILP is feasible, its optimal solution must be greater than or equal to 54.3
  32. Q33If the ILP is feasible, its optimal solution must be less than or equal to 54.3.
  33. Q34It is possible that the ILP’s optimal solution (if it exists) will be 50 ×10²³³¹.
  34. Q35It is possible that the ILP’s optimal solution (if it exists) will also be 54.3.
  35. Q36The ILP is guaranteed to be feasible.
  36. Q37What is the size of each Ai?
  37. Q38Based on the above data, answer the given subquestions.
  38. Q39Based on the above data, answer the given subquestions.
  39. Q40For n = 4, calculate the number of sequences of length 3 consisting only of numbers 0, 1, and 2 such that each number o…
  40. Q41For n = 6, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number o…
  41. Q42How many numbers in the interval [1; r] are divisible by pi ? The answer to this question is:
  42. Q43The final answer is:
  43. Q44A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  44. Q45A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  45. Q46A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  46. Q47A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  47. Q48A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  48. Q49A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  49. Q50A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  50. Q51A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  51. Q52A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  52. Q53A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…