Greedy and Divide and Conquer Questions and Answers

Answer: C

The root's cost is 31.

In the branch and bound TSP method, the root's lower bound is the total amount subtracted in reducing the cost matrix. Row minima: 3, 6, 7 and 10, total 26. After subtracting them the rows become (∞, 0, 2, 7), (5, ∞, 0, 2), (9, 0, ∞, 13) and (3, 2, 0, ∞).

Column minima of the reduced matrix: column 1 has 3, column 2 has 0, column 3 has 0 and column 4 has 2, total 5.

\[ \hat{C}(\text{root}) = 26 + 5 = 31 \]

26 is only the row reduction, without the column step. 29 and 36 come from arithmetic slips in the reductions.

Answer: B

The technique is Decrease and Conquer.

Decrease and conquer, as Levitin defines it, exploits the relationship between the solution to a problem instance and the solution to a smaller instance of the same problem, solving the smaller one (top down or bottom up) and extending it. Insertion sort, binary search and Euclid's algorithm are examples, decreasing the size by a constant, by a constant factor or by a variable amount.

Divide and conquer splits a problem into several subproblems and combines their solutions. Transform and conquer changes the instance into a different, easier form, and dynamic programming stores the solutions of overlapping subproblems.

Answer: D

All three modifications are needed, so the answer is (i), (ii) and (iii).

The DFT and its inverse are

\[ \begin{aligned} y_k &= \sum_{j=0}^{n-1} a_j\, \omega_n^{kj} \\ a_j &= \frac{1}{n} \sum_{k=0}^{n-1} y_k\, \omega_n^{-kj} \end{aligned} \]

Comparing the two, the inverse is the same computation with the roles of a and y switched (i), with \(\omega_n\) replaced by \(\omega_n^{-1}\) (ii), and with the result divided by n (iii). So the FFT computes the inverse DFT in \(\Theta(n \log n)\) time with all three changes; leaving out any one gives the wrong result.

Answer: D

The keyed answer is P→III, Q→IV, R→I, S→II.

• Merge sort is divide and conquer: split, sort the halves, merge.
• Insertion sort is decrease and conquer: sort n - 1 elements, then insert the last.
• Prim's algorithm is greedy: it always adds the cheapest edge leaving the tree.

Kruskal's algorithm is in fact also greedy, adding the cheapest edge that does not form a cycle, so pairing it with dynamic programming is not accurate. But each strategy in Group 2 is used once, and option D is the only one that matches merge sort, insertion sort and Prim's algorithm correctly. Every other option already fails on these: A makes insertion sort dynamic programming, and B and C give merge sort the wrong strategy.

Answer: C

Merge sort uses divide and conquer.

It divides the array into two halves, sorts each half recursively, and merges the two sorted halves in linear time, giving \(O(n \log n)\) time.

It does not explore and undo choices (backtracking), it has no overlapping subproblems to store (dynamic programming), and it is far more efficient than trying all orderings (brute force).

Answer: C

A greedy algorithm makes decisions based on local information.

At each step a greedy algorithm takes the choice that looks best at that moment (the locally optimal choice) and never revisits it, hoping this leads to a good overall solution.

It does not use global information, it does not always give the optimal solution (it does for some problems, such as minimum spanning trees, but not for the 0/1 knapsack), and it does not backtrack.

Answer: B

Backtracking builds a solution incrementally and removes those solutions that are not feasible.

Backtracking extends a partial solution one choice at a time and, as soon as a choice cannot lead to a valid solution, undoes it and tries the next. The N-queens problem and sudoku solving are typical uses.

It finds a valid solution but not necessarily the optimal one, it needs no sorting, and divide and conquer is a different strategy that splits a problem into independent subproblems.

Answer: C

The greedy approach solves the fractional knapsack problem.

When items can be divided, taking items in decreasing order of value per unit weight, and a fraction of the last one, is provably optimal. Sorting by that ratio gives an O(n log n) greedy solution.

In the 0/1 knapsack items cannot be split, and the greedy ratio rule can fail, so dynamic programming is used. Longest common subsequence and matrix chain multiplication are also classic dynamic programming problems, with no greedy choice that is always correct.

Answer: B

Huffman coding takes O(N log N) time.

The algorithm builds the tree by repeatedly removing the two lowest-frequency nodes from a priority queue and inserting their merged node. With a binary heap each removal or insertion costs O(log N), and there are about N - 1 merges, giving O(N log N) overall.

O(N) is possible only if the frequencies are already sorted and a two-queue method is used, which is not the general case. O(N (log N)^2) and O(N^2) overstate the cost of the heap version.

Answer: B

Merge sort uses DIVIDE AND CONQUER.

Merge sort divides the array into two halves, conquers each half by sorting it recursively, and combines the two sorted halves with a linear merge. That divide, conquer and combine structure is the definition of the paradigm, and it gives the recurrence T(n) = 2T(n/2) + n, so the running time is n log n.

Greedy algorithms make one locally best choice at a time, dynamic programming stores answers to overlapping subproblems, and branch and bound prunes a search tree. Merge sort's subproblems do not overlap and nothing is pruned.