Algorithms Homework Help?!?!

Algorithms Homework Help?!?!

[willmann817]

I am given an Array that contains the number of M&Ms of each color I have.  Each index in the array represents a different color.  I am also given an Integer of the number of children I am having at a birthday party. 

--THE CHILDREN MUST ALL HAVE THE SAME NUMBER OF M&MS
--EACH CHILD MUST ONLY HAVE 1 COLOR OF M&MS

Given an array containing the number of M&Ms I have in each available color, and the number of kids, determine the maximum number of M&Ms you can put in each goody bag. 
For example, with 11 red M&Ms, 9 blue M&Ms, and 5 M&Ms, you could give 5 children a maximum of 4 M&Ms each. You could not give each child 5 M&Ms without at least one child receiving M&Ms of different colors. 

  I was given a hint that said to write a helper function Groups(M : Integer; A : Int_Array) that takes a number of M&Ms and the array and returns how many groups I can make of M pieces of M&Ms. 

(For example, with 11 red bricks, 9 blue bricks, and 5 green bricks, Groups(3) would return 7.)

Then do my binary search based on this helper function(Posted below). 
--This problem MUST include Binary Search in some way.

I completed that but now I am stuck on the main function(also posted below) it is totally wrong cause I can't even pass the first test case:

	function Groups(Bricks : Integer; A: Int_Array) return Integer is
	counter : Integer := 0;
	begin
		for I in A'Range loop
			counter := counter + (A(I)/Bricks);
		end loop;
	return counter;

   function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
	lo : Integer := 1;
	hi : Integer := 50000;
	mid : Integer;
	begin
		for I in MsPerColor'Range loop
			if  MsPerColor(I) > hi then
				hi :=  MsPerColor(I);
			end if;
			if  MsPerColor(I) < lo then
				lo :=  MsPerColor(I);
			end if;
		end loop;

		mid := (lo+hi)/2;
		while Groups(mid, MsPerColor) /= Kids loop
			mid := (lo+hi)/2;
			if Groups(mid, MsPerColor) > Kids then
				hi := mid;
			else
				lo := mid;
			end if;
		end loop;
	return mid;
   end Candy;
	end Groups;

Re: Algorithms Homework Help?!?!

[Adam Beneschan]

On Tuesday, January 15, 2013 1:52:44 PM UTC-8, willmann817 wrote:
> I am given an Array that contains the number of M&Ms of each color I have.  Each index in the array represents a different color.  I am also given an Integer of the number of children I am having at a birthday party. 
> 
> --THE CHILDREN MUST ALL HAVE THE SAME NUMBER OF M&MS
> --EACH CHILD MUST ONLY HAVE 1 COLOR OF M&MS
> 
> Given an array containing the number of M&Ms I have in each available color, and the number of kids, determine the maximum number of M&Ms you can put in each goody bag. 
> 
> For example, with 11 red M&Ms, 9 blue M&Ms, and 5 M&Ms, you could give 5 children a maximum of 4 M&Ms each. You could not give each child 5 M&Ms without at least one child receiving M&Ms of different colors. 


I think the first approach should be to put the M&M's away.  If you give them to small children, they will get the chocolate all over their hands and then get it all over your furniture, curtains, pets, etc.  Don't buy the "melts in your mouth, not in your hand" garbage.  Maybe you're not old enough to remember that slogan.  But it doesn't work with little kids.  Trust me.


>   I was given a hint that said to write a helper function Groups(M : Integer; A : Int_Array) that takes a number of M&Ms and the array and returns how many groups I can make of M pieces of M&Ms. 
> 
> (For example, with 11 red bricks, 9 blue bricks, and 5 green bricks, Groups(3) would return 7.)


Ah, so you ate all the M&Ms yourself and decided to give them Legos instead.  Good, that's what I would have done.

  
> Then do my binary search based on this helper function(Posted below). 
> 
> --This problem MUST include Binary Search in some way.
> 
> 
> 
> I completed that but now I am stuck on the main function(also posted below) it is totally wrong cause I can't even pass the first test case:
> 
> 
> 
> 	function Groups(Bricks : Integer; A: Int_Array) return Integer is
> 	counter : Integer := 0;
> 	begin
> 		for I in A'Range loop
> 			counter := counter + (A(I)/Bricks);
> 		end loop;
> 	return counter;
        end Groups;  -- (obviously this line belonged up here)
> 
>    function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
> 	lo : Integer := 1;
> 	hi : Integer := 50000;
> 	mid : Integer;
> 	begin
> 		for I in MsPerColor'Range loop
> 			if  MsPerColor(I) > hi then
> 				hi :=  MsPerColor(I);
> 			end if;
> 
> 			if  MsPerColor(I) < lo then
> 				lo :=  MsPerColor(I);
> 			end if;
> 		end loop;
> 
> 		mid := (lo+hi)/2;
> 		while Groups(mid, MsPerColor) /= Kids loop
> 			mid := (lo+hi)/2;
> 			if Groups(mid, MsPerColor) > Kids then
> 				hi := mid;
> 			else
> 				lo := mid;
> 			end if;
> 		end loop;
> 	return mid;
>    end Candy;

I won't give the whole answer, since this is a homework assignment.  But it will probably help to put some lines in the code to output some values.  I did that myself, since I was in too big a hurry to study your code carefully.  I added these after the "while" line:

text_io.put("lo=" & integer'image(lo));
text_io.put(" hi=" & integer'image(hi));
text_io.put(" mid=" & integer'image(mid));
text_io.put_line(" groups returns " & integer'image(Groups(mid, MsPerColor)));

If you do this, I think you'll quickly figure out what the first mistake is.

As for the second mistake: the Put statements should help you see that too.  You need to think about: what kinds of quantities do your variables lo, hi, and mid represent, and what kind of quantity does the first parameter to Groups represent.  They don't match, which is a problem.

Good luck, and hope this helps,

                             -- Adam

Re: Algorithms Homework Help?!?!

[Shark8]

Um, there's nothing there suggestive of a binary-search, or ANY search.
But here's an example of how to do the groupings.

Pragma Ada_2012;

With
Ada.Text_IO,
Ada.Text_IO.Text_Streams;

Procedure Test is

    Type Color is ( Red, Blue, Green, Yellow, Brown );

    Type MM_Array is Array(Color Range <>) of Natural;
    
    --------------------------
    -- Forward Declarations --
    --------------------------
    
    Function Maximum( Candy : MM_Array ) Return Natural
      with Pre => Candy'Length in Positive;
    
    Function Group( Group_Size : Positive; Candy : MM_Array ) Return Natural
      with Pre => Candy'Length in Positive AND Maximum(Candy) >= Group_Size;
    

    -----------------------
    --  Function Bodies  --
    -----------------------
    
    Function Maximum( Candy : MM_Array ) Return Natural is
    begin
	Return Result : Natural := Natural'First do
	    For Value of Candy loop
		Result:= Natural'Max( Result, Value );
	    End loop;
	End return;
    end Maximum;
    
    Function Group( Group_Size : Positive; Candy : MM_Array ) Return Natural is
    begin
	Return Result : Natural := 0 do
	    For Value of Candy loop
		Result:= Result + Value / Group_Size;
	    End loop;
	End return;
    end Group;
    
    Candies : MM_Array := (Red => 11, Blue => 9, Green => 5);
Begin
    Ada.Text_IO.New_Line;
    Ada.Text_IO.Put_Line( "Max:  " & Maximum(Candies)'Img  );
    Ada.Text_IO.Put_Line( "Group:" & Group(8, Candies)'Img  );
End Test;

Re: Algorithms Homework Help?!?!

[willmann817]

On Tuesday, January 15, 2013 5:50:37 PM UTC-5, Adam Beneschan wrote:
> On Tuesday, January 15, 2013 1:52:44 PM UTC-8, willmann817 wrote:
> 
> > I am given an Array that contains the number of M&Ms of each color I have.  Each index in the array represents a different color.  I am also given an Integer of the number of children I am having at a birthday party. 
> 
> > 
> 
> > --THE CHILDREN MUST ALL HAVE THE SAME NUMBER OF M&MS
> 
> > --EACH CHILD MUST ONLY HAVE 1 COLOR OF M&MS
> 
> > 
> 
> > Given an array containing the number of M&Ms I have in each available color, and the number of kids, determine the maximum number of M&Ms you can put in each goody bag. 
> 
> > 
> 
> > For example, with 11 red M&Ms, 9 blue M&Ms, and 5 M&Ms, you could give 5 children a maximum of 4 M&Ms each. You could not give each child 5 M&Ms without at least one child receiving M&Ms of different colors. 
> 
> 
> 
> 
> 
> I think the first approach should be to put the M&M's away.  If you give them to small children, they will get the chocolate all over their hands and then get it all over your furniture, curtains, pets, etc.  Don't buy the "melts in your mouth, not in your hand" garbage.  Maybe you're not old enough to remember that slogan.  But it doesn't work with little kids.  Trust me.
> 
> 
> 
> 
> 
> >   I was given a hint that said to write a helper function Groups(M : Integer; A : Int_Array) that takes a number of M&Ms and the array and returns how many groups I can make of M pieces of M&Ms. 
> 
> > 
> 
> > (For example, with 11 red bricks, 9 blue bricks, and 5 green bricks, Groups(3) would return 7.)
> 
> 
> 
> 
> 
> Ah, so you ate all the M&Ms yourself and decided to give them Legos instead.  Good, that's what I would have done.
> 
> 
> 
>   
> 
> > Then do my binary search based on this helper function(Posted below). 
> 
> > 
> 
> > --This problem MUST include Binary Search in some way.
> 
> > 
> 
> > 
> 
> > 
> 
> > I completed that but now I am stuck on the main function(also posted below) it is totally wrong cause I can't even pass the first test case:
> 
> > 
> 
> > 
> 
> > 
> 
> > 	function Groups(Bricks : Integer; A: Int_Array) return Integer is
> 
> > 	counter : Integer := 0;
> 
> > 	begin
> 
> > 		for I in A'Range loop
> 
> > 			counter := counter + (A(I)/Bricks);
> 
> > 		end loop;
> 
> > 	return counter;
> 
>         end Groups;  -- (obviously this line belonged up here)
> 
> > 
> 
> >    function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
> 
> > 	lo : Integer := 1;
> 
> > 	hi : Integer := 50000;
> 
> > 	mid : Integer;
> 
> > 	begin
> 
> > 		for I in MsPerColor'Range loop
> 
> > 			if  MsPerColor(I) > hi then
> 
> > 				hi :=  MsPerColor(I);
> 
> > 			end if;
> 
> > 
> 
> > 			if  MsPerColor(I) < lo then
> 
> > 				lo :=  MsPerColor(I);
> 
> > 			end if;
> 
> > 		end loop;
> 
> > 
> 
> > 		mid := (lo+hi)/2;
> 
> > 		while Groups(mid, MsPerColor) /= Kids loop
> 
> > 			mid := (lo+hi)/2;
> 
> > 			if Groups(mid, MsPerColor) > Kids then
> 
> > 				hi := mid;
> 
> > 			else
> 
> > 				lo := mid;
> 
> > 			end if;
> 
> > 		end loop;
> 
> > 	return mid;
> 
> >    end Candy;
> 
> 
> 
> I won't give the whole answer, since this is a homework assignment.  But it will probably help to put some lines in the code to output some values.  I did that myself, since I was in too big a hurry to study your code carefully.  I added these after the "while" line:
> 
> 
> 
> text_io.put("lo=" & integer'image(lo));
> 
> text_io.put(" hi=" & integer'image(hi));
> 
> text_io.put(" mid=" & integer'image(mid));
> 
> text_io.put_line(" groups returns " & integer'image(Groups(mid, MsPerColor)));
> 
> 
> 
> If you do this, I think you'll quickly figure out what the first mistake is.
> 
> 
> 
> As for the second mistake: the Put statements should help you see that too.  You need to think about: what kinds of quantities do your variables lo, hi, and mid represent, and what kind of quantity does the first parameter to Groups represent.  They don't match, which is a problem.
> 
> 
> 
> Good luck, and hope this helps,
> 
> 
> 
>                              -- Adam

Adam,

Here is what I am seeing:
There are many more of this before what I have posted below
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46 mid= 45 groups returns  1
lo= 45 hi= 46*** Failed Test #2 ***
   Kids = 10
   BricksPerColor = (6,2,3,46,2)
   Time limit exceeded.
   Your code may be stuck in an infinite loop, or may just be too slow.
Failure limit reached.  Aborting remaining tests.

Can you maybe give me a guiding hint on what needs to be done to fix this.  I do not want code or an answer but.  I think the binary search is searching for the value of mid that makes Groups(mid,BricksPerColor) = Kids.  If that is incorrect then that is the first place I need help.

Thanks.

Re: Algorithms Homework Help?!?!

[Jeffrey Carter]

On 01/15/2013 02:52 PM, willmann817 wrote:
>
>     function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
> 	lo : Integer := 1;
> 	hi : Integer := 50000;
> 	mid : Integer;
> 	begin
> 		for I in MsPerColor'Range loop
> 			if  MsPerColor(I) > hi then
> 				hi :=  MsPerColor(I);
> 			end if;
> 			if  MsPerColor(I) < lo then
> 				lo :=  MsPerColor(I);
> 			end if;
> 		end loop;

Will you ever have more than 50,000 M&Ms of any one color? If not, then Hi will 
remain 50,000. Will you ever have less than 1 M&M of any one color? If not, then 
Lo will remain 1.

-- 
Jeff Carter
"My legs are gray, my ears are gnarled, my eyes are old and bent."
Monty Python's Life of Brian
81

Re: Algorithms Homework Help?!?!

[willmann817]

On Tuesday, January 15, 2013 6:54:19 PM UTC-5, Jeffrey Carter wrote:
> On 01/15/2013 02:52 PM, willmann817 wrote:
> 
> >
> 
> >     function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
> 
> > 	lo : Integer := 1;
> 
> > 	hi : Integer := 50000;
> 
> > 	mid : Integer;
> 
> > 	begin
> 
> > 		for I in MsPerColor'Range loop
> 
> > 			if  MsPerColor(I) > hi then
> 
> > 				hi :=  MsPerColor(I);
> 
> > 			end if;
> 
> > 			if  MsPerColor(I) < lo then
> 
> > 				lo :=  MsPerColor(I);
> 
> > 			end if;
> 
> > 		end loop;
> 
> 
> 
> Will you ever have more than 50,000 M&Ms of any one color? If not, then Hi will 
> 
> remain 50,000. Will you ever have less than 1 M&M of any one color? If not, then 
> 
> Lo will remain 1.
> 
> 
> 
> -- 
> 
> Jeff Carter
> 
> "My legs are gray, my ears are gnarled, my eyes are old and bent."
> 
> Monty Python's Life of Brian
> 
> 81
Jeff I changed the initial values of lo and hi but there is still something getting me stuck in an infinite loop.
	lo : Integer := Integer'Last; 
	hi : Integer := Integer'First;

Re: Algorithms Homework Help?!?!

[willmann817]

On Tuesday, January 15, 2013 7:01:59 PM UTC-5, willmann817 wrote:
> On Tuesday, January 15, 2013 6:54:19 PM UTC-5, Jeffrey Carter wrote:
> 
> > On 01/15/2013 02:52 PM, willmann817 wrote:
> 
> > 
> 
> > >
> 
> > 
> 
> > >     function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
> 
> > 
> 
> > > 	lo : Integer := 1;
> 
> > 
> 
> > > 	hi : Integer := 50000;
> 
> > 
> 
> > > 	mid : Integer;
> 
> > 
> 
> > > 	begin
> 
> > 
> 
> > > 		for I in MsPerColor'Range loop
> 
> > 
> 
> > > 			if  MsPerColor(I) > hi then
> 
> > 
> 
> > > 				hi :=  MsPerColor(I);
> 
> > 
> 
> > > 			end if;
> 
> > 
> 
> > > 			if  MsPerColor(I) < lo then
> 
> > 
> 
> > > 				lo :=  MsPerColor(I);
> 
> > 
> 
> > > 			end if;
> 
> > 
> 
> > > 		end loop;
> 
> > 
> 
> > 
> 
> > 
> 
> > Will you ever have more than 50,000 M&Ms of any one color? If not, then Hi will 
> 
> > 
> 
> > remain 50,000. Will you ever have less than 1 M&M of any one color? If not, then 
> 
> > 
> 
> > Lo will remain 1.
> 
> > 
> 
> > 
> 
> > 
> 
> > -- 
> 
> > 
> 
> > Jeff Carter
> 
> > 
> 
> > "My legs are gray, my ears are gnarled, my eyes are old and bent."
> 
> > 
> 
> > Monty Python's Life of Brian
> 
> > 
> 
> > 81
> 
> Jeff I changed the initial values of lo and hi but there is still something getting me stuck in an infinite loop.
> 
> 	lo : Integer := Integer'Last; 
> 
> 	hi : Integer := Integer'First;

Nevermind everyone I got the answer and figured it out with hints one of my classmates.

Re: Algorithms Homework Help?!?!

[Robert A Duff]

willmann817 <willmann817@gmail.com> writes:

> Then do my binary search based on this helper function(Posted below). 
> --This problem MUST include Binary Search in some way.

That seems like an odd requirement.  Taken literally, it would mean
you could do a binary search on some unrelated data structure,
throw away the result, and then solve the real problem some other
(slower) way.  But that's probably not what your teacher meant.  ;-)

If I were the teacher, I'd say:

    The program must run in O(log N) time, where N is ....
    Note: binary search is an O(log N) algorithm.

- Bob

Re: Algorithms Homework Help?!?!

[Adam Beneschan]

On Wednesday, January 16, 2013 11:47:37 AM UTC-8, Robert A Duff wrote:
> 
> > Then do my binary search based on this helper function(Posted below). 
> > --This problem MUST include Binary Search in some way.
> 
> That seems like an odd requirement.  Taken literally, it would mean
> you could do a binary search on some unrelated data structure,
> throw away the result, and then solve the real problem some other
> (slower) way.  But that's probably not what your teacher meant.  ;-)
> 
> If I were the teacher, I'd say:
> 
>     The program must run in O(log N) time, where N is ....
>     Note: binary search is an O(log N) algorithm.

When I studied computer science, binary search was something covered in, I think, one of the first-year introductory courses.  Algorithmic analysis was an upper-division course, which I think I took in my third year.  So I don't think this would work.  If this is (as I suspect) an introductory course, the students may not yet even know what O-notation is, let alone know what the expected running time for algorithms is.  (OK, you've given them the hint that binary search is O(log N); but if they don't know what the run time is for other algorithms, it won't help them if you say "You don't have to use binary search; you can use some other algorithm that runs in O(log N) time".)

On top of that, I don't think this homework assignment can be done with an O(log N) algorithm.  It takes an input array that isn't required to be sorted, so there has to be some part of the program that iterates through the entire array.  In the OP's first program, he put his binary search in a while loop, and the expected number of iterations would be O(log N) [I'm not sure what N is]; but his loop called a function that scanned through the array, so the actual time is O(N log N) or O(M log N) or something.  I haven't studied the problem in depth to figure out what the best running time is.  It's probably independent of the largest value in the array, while I think the binary search the OP came up with started with an interval based on the largest value in the array, and successively divided it in half to find the answer.

Anyway, I'd tend to agree that it seems odd to *require* binary search, especially since off the top of my head it doesn't seem appropriate for this particular problem.  But classroom problems do have to be contrived, sometimes.  

                         -- Adam

Re: Algorithms Homework Help?!?!

[Robert A Duff]

Adam Beneschan <adam@irvine.com> writes:

> When I studied computer science, binary search was something covered
> in, I think, one of the first-year introductory courses.  Algorithmic
> analysis was an upper-division course, which I think I took in my
> third year.  So I don't think this would work.  If this is (as I
> suspect) an introductory course, the students may not yet even know
> what O-notation is, let alone know what the expected running time for
> algorithms is.  (OK, you've given them the hint that binary search is
> O(log N); but if they don't know what the run time is for other
> algorithms, it won't help them if you say "You don't have to use
> binary search; you can use some other algorithm that runs in O(log N)
> time".)

Good point.  I don't actually remember when I learned to program a
binary search, nor when I learned O-notation.  It seems like I've
always known these things (and I've always known how to read, and
I've always been happily married to my wife).  ;-)

Of course I knew how to do a binary search long before I knew how
to program one -- it's more-or-less how one found things in a dictionary
before google.  It's interesting that when programming a binary
search, people often write infinite loops and similar silly mistakes,
but when doing it by hand, those mistakes don't occur.

> On top of that, I don't think this homework assignment can be done
> with an O(log N) algorithm. ...

Oh, OK.  I didn't look at it carefully.  It just struck me that
in the real world, customers don't say "Please solve this problem
with a binary search"; they say "Please solve it fast enough",
possibly with a vague or precise notion of "fast enough".

> Anyway, I'd tend to agree that it seems odd to *require* binary
> search, especially since off the top of my head it doesn't seem
> appropriate for this particular problem.  But classroom problems do
> have to be contrived, sometimes.

True.

- Bob

Re: Algorithms Homework Help?!?!

[Adam Beneschan]

On Wednesday, January 16, 2013 2:27:48 PM UTC-8, Robert A Duff wrote:

> > On top of that, I don't think this homework assignment can be done
> > with an O(log N) algorithm. ...
> 
> Oh, OK.  I didn't look at it carefully.

I looked at it a bit more.  There are two variables involved: the size of the array, and the largest number in the array.  My gut feeling was that the algorithm's time shouldn't depend on the largest value in the array.  But I'm no  longer sure.  The issue boils down to this: Suppose you have an array A(1..m) of positive integers; you can define a function f(n) = floor(A(1)/n) + floor(A(2)/n) + ... + floor(A(m)/n).  This is monotonically nonincreasing.  The problem is, given some value K, to find the largest n such that f(n) >= K.  Finding the best way to solve this problem seems like an interesting problem in number theory, and I don't know how to solve it.  Given that, and since the function is nonincreasing, using a binary search to find the answer seems reasonable.  Maybe there's a better way, though.

                            -- Adam

Re: Algorithms Homework Help?!?!

[ajim]

Hie friends, this is ajim..I think friend you should put your efforts to the home work help. If you are really looking for the help then you can check some online websites like acropolismentors.

Re: Algorithms Homework Help?!?!

[ajim]

Hie friends, this is ajim..I think friend you should put "your" efforts to the home work help. If you are really looking for the help then you can check some online websites like acropolismentors, because when i got trapped in such problems then i always go to the acropolismentors site.