I need help with this homework question as it is really confusing to me. Questio
ID: 668236 • Letter: I
Question
I need help with this homework question as it is really confusing to me.
Question: Given a candy bar with x × y pieces making up the bar. You need to break it into xy 1 × 1 pieces to share with xy people. You can only break it in a straight line, and once broken, only one piece at a time can be further broken. Design an algorithm that solves the problem with the minimum number of bar breaks. What is this minimum number? Justify your answer by using properties of a binary tree.
and the hint that my instructor gave us is use the divide and conquer method.
Thanks!
Explanation / Answer
Its a simple and straight forward question guys. Nothing to worry much on this.
As the candy bar is holding x*y pieces, it can be easily distributed to x*y people (one each) so easily.
The only thing is, how to break down the bar into pieces.
Your requirement is:
As you hinted me to use the divide and conquer, I am introducing the terminology for you. Ofcourse we should divide it.
Divide and conquer logic goes like this:
Given a bar of size x*y (Consider it x column and rows.)
Note: As you want to minimize the number of breaks, please do consider applying this logic before moving further:
if(y>x)
temp = x.
x = y.
y = temp.
This ensures that you are breaking the more lengthiest side first.
Algorithm for dividing x columns: Assign low = 1(the left column value), high = x(right column value).
AlgorithmMidSplitColumns (low,high)
Stop.
Given x number of rows, this logic runs for x-1 number of times. An instances shows like this:
x = 10: (1-10 columns)
Calculate the mid: (1+10)/2 /*5*/
1.Break it to 2 pieces. /*1-5*/ /*6-10*/
(1-5) (6-10)
mid:= (1+5)/2 /*3*/ mid:= (6+10)/2 /*8*/
2.Break into 2 pieces./*1-3*//*4-5*/ 3.Break into 2 pieces. /*6-8*//*9-10*/
(1-3) (4-5) (6-8) (9-10)
mid=(1+3)/2/*2*/ mid=(4+5)/2 /*4*/ mid=(6+8)/2 /*7*/mid=(9+10)/2 /*9*/
4. /*1-2*//*3-3*/ 5./*4-4*/ 7/*5-5*/ 6. /*6-7*//*8-8*/ 7./*9-9*/ /*10-10*/
mid=(1+2)/2 /*1*/ mid=(6+7)/2 /*6*/
8. /*1-1*//*2-2*/ 9. /*6-6*/ /*7-7*/
Algorithm for dividing y rows: Assign low = 1(the left row value), high = y(right row value).
AlgorithmSplitRows (low,high)
1. if high=1 /*If only one row is left.*/
Stop.
2. high = high-1. /*Break one piece further.*/
3. AlgorithmSplitRows(low,high-1) /*Apply the same logic for y-1 bar.*/
AlgorithmSplitColumns() requires a total of x-1 splits.
Further for each column when applying AlgorithmSplitRows() it requires y-1 splits.
Therefore the total number of split requires is exactly equal to:
(x-1) + ((x-1) * (y-1) )
I tried to apply two different techniques (Binary division for column split, and Linear division for row split). Ofcourse this is not necessary as you have to split all the pieces, you can just employ on one technnique for both row and column splits. As the effiency of both the algorithms in this case is n-1.