Home / Study library / Advanced Algorithms / End Term · May 2025 Advanced Algorithms · End Term · May 2025 · FN
Advanced Algorithms · End Term · May 2025 FN
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
0 / 21 published solutions
Q26 Q27 Q28 Q29 Q30 Q31 Q32 Q33 Q34 Q35 Q36 Q37 Q38 Q39 Q40 Q41 Q42 Q43 Q44 Q45 Q46 Question 26 MCQ · 3.0 marks 6406534739723. Neither algorithm always correctly determines whether or not a given tree
graph has a perfect matching.
6406534739724. Both algorithms always correctly determine whether or not a given tree graph
has a perfect matching.
6406534739725. Algorithm B always correctly determines whether or not a given tree graph
has a perfect matching; algorithm A does not.
6406534739726. Algorithm A always correctly determines whether or not a given tree graph
has a perfect matching; algorithm B does not.
A published solution is not available for this question yet.
Report a correction for Q26
Question 27 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Report a correction for Q27
Question 28 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Report a correction for Q28
Question 29 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
A published solution is not available for this question yet.
Report a correction for Q29
Question 30 NAT · 2.0 marks
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.
A published solution is not available for this question yet.
Report a correction for Q30
Question 31 NAT · 2.0 marks
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.
A published solution is not available for this question yet.
Report a correction for Q31
Question 32 MSQ · 3.0 marks 6406534739741. It is in P.
6406534739742. It is in NP.
6406534739743. It is NP-hard.
6406534739744. It is NP-complete.
A published solution is not available for this question yet.
Report a correction for Q32
Question 33 MSQ · 3.0 marks Choose the correct
6406534739747. 6406534739748. 6406534739749. A published solution is not available for this question yet.
Report a correction for Q33
Question 34 MCQ · 2.0 marks A published solution is not available for this question yet.
Report a correction for Q34
Question 35 MCQ · 3.0 marks A published solution is not available for this question yet.
Report a correction for Q35
Question 36 MCQ · 3.0 marks
Based on the above data, answer the given subquestions.
6406534739754. 6406534739755. 6406534739756. 6406534739757. A published solution is not available for this question yet.
Report a correction for Q36
Question 37 MCQ · 3.0 marks
Based on the above data, answer the given subquestions.
6406534739758. 6406534739759. 6406534739760. 6406534739761. A published solution is not available for this question yet.
Report a correction for Q37
Question 38 MCQ · 3.0 marks 6406534739762. 6406534739763. 6406534739764. 6406534739765. A published solution is not available for this question yet.
Report a correction for Q38
Question 39 MCQ · 2.0 marks 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 published solution is not available for this question yet.
Report a correction for Q39
Question 40 MCQ · 2.0 marks Consider the following statements and answer the given subquestions if they are true or false.
A published solution is not available for this question yet.
Report a correction for Q40
Question 41 MCQ · 2.0 marks Answer the given subquestions.
Every linear program has a unique optimal solution.
A published solution is not available for this question yet.
Report a correction for Q41
Question 42 MCQ · 2.0 marks Answer the given subquestions.
A published solution is not available for this question yet.
Report a correction for Q42
Question 43 MCQ · 2.0 marks Answer the given subquestions.
Consider the algorithm in the previous question no 18. Does the algorithm always output an
optimal vertex cover?
A published solution is not available for this question yet.
Report a correction for Q43
Question 44 MCQ · 2.0 marks Answer the given subquestions.
Consider the algorithm in the previous question no 18. Does the algorithm always output a 2-
approximate vertex cover?
A published solution is not available for this question yet.
Report a correction for Q44
Question 45 MCQ · 2.0 marks 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 published solution is not available for this question yet.
Report a correction for Q45
Question 46 MCQ · 3.0 marks 6406534739780. 6406534739781. 6406534739782. 6406534739783.
**DL(CV)**
**Section Id :** 64065399589
**Section Number :** 3
**Section type :** Online
**Mandatory or Optional :** Mandatory
A published solution is not available for this question yet.
Report a correction for Q46
