You are given an n x m chompo bar. Your goal is to devise an algorithm A that ta

Question

You are given an n x m chompo bar. Your goal is to devise an algorithm A that takes
as input (n,m) and returns the minimal number of cuts needed to divide the bar into
perfect squares of either 1x1, 2x2, 3x3, . . ., jxj. With each cut, you can split the bar either
horizontally or vertically. For example, A(2, 3) = 2 because 2x3 ---> (2x2, 1x2) ---> (2x2, 1x1,
1x1).
1. Notice that no matter the rectangle, it is always possible to make a perfect square in
the first cut. Show that this strategy fails. Namely, show an input size for which the
strategy of picking the cut which creates the largest box leads to extra cuts in total.
2. Devise a Dynamic Programming algorithm which determines the minimal number of cuts.

Explanation / Answer

we can form the largest square by first cut and further we will try making largest square and then small sqares.

Applying recursive functions

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.