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.

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

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