Greedy and Divide and Conquer Questions and Answers

Answer: A

It is a 2-approximation problem.

The standard approximation algorithm picks any remaining edge (u, v), puts both u and v in the cover, deletes every edge touching them, and repeats. The edges it picks share no vertices, and any vertex cover must contain at least one end of each of them, so the cover it builds is at most twice the size of the optimum.

The ratio 2 is tight, so the algorithm is classed as a 2-approximation. A bound of 3 is weaker and not how it is described, which rules out the 3-approximation and 'Both' options.

Answer: C

The number of comparisons needed in the worst case to find both the maximum and the minimum of n numbers is about \(\lceil 3n/2 \rceil - 2\), and option C is the closest listed form. Pair the elements, compare each pair (n/2 comparisons), then find the maximum among the winners and the minimum among the losers (about n/2 - 1 each).

\(2n - 2\) is what the naive method needs, \(n + \lfloor \lg n \rfloor - 2\) is the bound for finding the two largest elements, and \(2 \lg n - 2\) is too small to be possible.

Answer: B

The efficient algorithm for multiplying two \(n \times n\) matrices listed here has complexity \(O(n^{2.81})\), which is Strassen's algorithm. It uses 7 multiplications of half-size matrices instead of 8, giving \(O(n^{\log_{2} 7}) = O(n^{2.81})\).

\(O(n^{3})\) is the ordinary method, so it is not the efficient one. \(O(n^{2.67})\) is not a known result in this list, and \(O(n^{2})\) is the trivial lower bound, which no known algorithm achieves.