Greedy and Divide and Conquer Questions and Answers

Q: Let C^(x) denote the ranking function that associates cost with a node in Branch and Bound Formulation of Travelling Salesperson Problem. What is the value of C^(x) for the root node for the following problem instance ?12341∞3510211∞683167∞204131210∞

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.

Q: The technique that exploits the relationship between solution to the given instance of a problem and smaller instance of the same problem is known as :

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.

Q: The FFT (a) returns DFT (y). To compute inverse of DFT, FFT algorithm can be modified to :(i) Switch the roles of a and y(ii) Replace \(w_{n}\) by \(w_{n}^{-1}\)(iii) Divide the final result by n

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.

Q: Match the algorithms in Group 1 with the design strategy used by the algorithm in Group 2Group 1Group 2P. Merge SortI. Greedy StrategyQ. Insertion SortII. Dynamic ProgrammingR. Prim's algorithmIII. Divide and ConquerS. Kruskal's algorithmIV. Decrease and Conquer

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.

Q: The Merger sort algorithm employs the design technique :

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

Let C^(x) denote the ranking function that associates cost with a node in Branch and Bound Formulation of Travelling Salesperson Problem. What is the value of C^(x) for the root node for the following problem instance ?

	1	2	3	4
1	∞	3	5	10
2	11	∞	6	8
3	16	7	∞	20
4	13	12	10	∞

A.26
B.29
C.31
D.36

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

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.

Discuss in Forum

The technique that exploits the relationship between solution to the given instance of a problem and smaller instance of the same problem is known as :

A.Divide and Conquer
B.Decrease and Conquer
C.Transform and Conquer
D.Dynamic Programming

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

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.

Discuss in Forum

The FFT (a) returns DFT (y). To compute inverse of DFT, FFT algorithm can be modified to :

(i) Switch the roles of a and y
(ii) Replace \(w_{n}\) by \(w_{n}^{-1}\)
(iii) Divide the final result by n

A.(i) and (ii)
B.(i) and (iii)
C.(ii) and (iii)
D.(i), (ii) and (iii)

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

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.

Discuss in Forum

Match the algorithms in Group 1 with the design strategy used by the algorithm in Group 2

Group 1	Group 2
P. Merge Sort	I. Greedy Strategy
Q. Insertion Sort	II. Dynamic Programming
R. Prim's algorithm	III. Divide and Conquer
S. Kruskal's algorithm	IV. Decrease and Conquer

A.P→III, Q→II, R→I, S→IV
B.P→I, Q→III, R→II, S→IV
C.P→IV, Q→III, R→II, S→I
D.P→III, Q→IV, R→I, S→II

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

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.

Discuss in Forum

The Merger sort algorithm employs the design technique :

A.Backtracking
B.Dynamic programming
C.Divide and Conquer
D.Brute force

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

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

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Greedy and Divide and Conquer Questions and Answers || Greedy and Divide and Conquer MCQ Questions and Answers || Greedy and Divide and Conquer GK Questions and Answers || Greedy and Divide and Conquer GK MCQ Questions || Greedy and Divide and Conquer Multiple Choice Questions and Answers || Greedy and Divide and Conquer GK || GK on Greedy and Divide and Conquer || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Greedy and Divide and Conquer Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications