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.

Answer: D

The file can be encoded with 2,24,000 bits. Merging the two smallest frequencies repeatedly (5 and 9 give 14; 12 and 13 give 25; 14 and 16 give 30; 25 and 30 give 55; 45 and 55 give 100) gives the code lengths g = 1, h = 3, i = 3, j = 3, k = 4 and l = 4.

\[ 45(1) + 13(3) + 12(3) + 16(3) + 9(4) + 5(4) \]

\[ = 45 + 39 + 36 + 48 + 36 + 20 = 224 \]

That is 224 thousand bits. The other figures are above the Huffman optimum, so option (D) is the answer; a fixed three-bit code would use 3,00,000 bits.

Answer: C

Both statements are not correct. The 0-1 knapsack problem cannot be solved correctly by the greedy method of choosing items by value to weight ratio, since a whole item must be taken or left, and it needs dynamic programming. The fractional knapsack problem is solved by the greedy method, which takes items in the order of their value to weight ratio, so dynamic programming is not the efficient way.

Each statement swaps the method, so both are wrong, and the other options are wrong.

Answer: B

The optimal (Huffman) code gives an average length of 2.15 bits. Merging the two smallest probabilities again and again: 0.08 + 0.12 = 0.20, then 0.15 + 0.20 = 0.35, then 0.25 + 0.35 = 0.60, then 0.40 + 0.60 = 1. The code lengths are 1 for 0.40, 2 for 0.25, 3 for 0.15 and 4 for each of 0.12 and 0.08.

A fixed-length code would need 3 bits, which is why 3.4 and 3.8 are too large.

Answer: B

The maximum profit is 38.

The profit to weight ratios are 5, 2.5, 2 and 2, so a greedy fractional knapsack takes objects 1, 2 and 3 whole, using weight \(2 + 4 + 6 = 12\) and earning \(10 + 10 + 12 = 32\). The remaining capacity of 3 is filled with 3/9 of object 4, which earns \(18 \times \frac{3}{9} = 6\), so the total is \[ 32 + 6 = 38. \]

32 is the profit without the fraction, and 40 and 30 do not arise.