Pennies Pennies Dimes Pennies

Problem
You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:

L

If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.

R

If the right pile has an even number of pannies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed. 

------------------------------------------------------------------------------------------------------------
Answer

What are we given:

 We have 64 pennies at the start in the left drawer

What are we trying to accomplish:

   Have a drawer with only 48 coins.          .

Limitations:

  The only operation one can do is to remove half of the coins from one drawer and move it into the other drawer.

Final Result::

At the start I was too focused on trying to find a way from working top to bottom, when I completely brushed off the idea that I could have went from bottom top. Instead of trying every possible way of getting the drawer to size 48, we can try to start from 48 coins and make some drawer with all 64 coins.

So lets think about this logically. If we have one drawer with 48 coins, the other drawer MUST have 16 coins. We`ll call the drawer that has 48 coins 'Drawer A' and the drawer with 16 coins 'Drawer B'. Now we have to reverse engineer the rules given in the problem. We are only allowed to remove half of the coins from a drawer at a time. This would mean that, if I removed half the coins in drawer Y (an arbitrary drawer), drawer Z would have Y's current number of coins plus the coins that already existed in its own drawer (if it had any). This basically means that the number of coins in Y  after the swapping, can NEVER be more than the number of coins in Z.

Now lets look at our current situation. We have Drawer A with 48 coins and Drawer B with 16 coins. We just concluded that, after the swap, drawer y can never be more than the coins in drawer z. This means that the last transition in our problem could have never been from A--> B, meaning, the last transition was cutting Drawer B's coins in half.

So to 'undo' this move, we must double B's number of coins, and subtract A's coins by the amount of coins we increased B by. So our current situation is:  Drawer A: 32   Drawer B: 32. At this point we can see that both drawers have the same number of coins. This only means one thing; one drawer had all of the coins at a point, and it has been split by half and separated between the two drawers. Thus we can state that one drawer had 64 coins in total.

So is there a way to find a set of numbers in which this technique work? What are the different number of starting number of pennies can we have that could lead us to having a drawer with 48 coins while only using these 2 rules? Is there a relationship between the values?

Lets try experimenting.
* it is important to note that the drawer which had the lower amount of coins must be the one that keeps gaining coins. If there is a point where that drawer exceeds the amount of coins in the other drawer, it is impossible to get one drawer with all the coins. The reason for this is because if you increase drawer B, and it exceeds the other drawer, you'll be rotating back and forth between two numbers.

Example:
Drawer A has 48 coins.      Drawer B has 12 coins.
Drawer A has 36 coins    Drawer B has 24 coins  
Drawer A has 12 coins    Drawer B has 48 coins    
Drawer A has 24 coins    Drawer B has 36 coins    

The beauty of trying it bottom top is that there is only one possible way you can move. You don't have to debate on whether you should do it one way or another. So it is guaranteed that this won't work.

Then there are two cases. The drawer with 48 coins is the smallest, or the other drawer is the smallest.

Case 1: #Drawer with 48 coins is the bigger drawer
That means, the pattern should follow this structure. At at any point, if one of the drawers were to be 0, then we have a winner.
Drawer A has 48 coins.      Drawer B has x coins.
Drawer A has 48-3x coins    Drawer B has 4x coins  
Drawer A has 48-7x coins    Drawer B has 8x coins  
Drawer A has 48-15x coins    Drawer B has 16x coins  
.
.
.
.
.
Drawer A has  48 - [ (2^t) - 1 ]*x   Drawer B has 2^t * x  coins      where t is the turn number
.
.
rewritten:
Drawer A has  48 -  x(2^t) - x    Drawer B has x(2^t)   coins      where t is the turn number

So if Drawer A is the drawer with the most coins at the start, if there exists a t such that 48 -  x(2^t) - x = 0, where x is the number of coins in the other drawer at the start, it is possible for 48 + x coins to be in one drawer at turn t. If not, it is impossible.

         

Case 1: #Drawer with 48 coins is the smallerdrawer
That means, the pattern should follow this structure. At at any point, if one of the drawers were to be 0, then we have a winner.
Drawer A has 48 coins.      Drawer B has x coins.
Drawer A has 96 coins    Drawer B has x - 48 coins  
Drawer A has 192 coins    Drawer B has x - 48 - 96 coins  
Drawer A has 384 coins    Drawer B has x - 48 - 96 - 192 coins  
.
.
.
.
.
Drawer A has  (2^t)*48      Drawer B has x - 48(2^t - 1)  coins      where t is the turn number

So if Drawer A is the drawer with the lestcoins at the start, if there exists a t such that x - 48(2^t - 1) = 0  where x is the number of coins in the other drawer at the start, it is possible for 48 + x coins to be in one drawer at turn t. If not, it is impossible.


Either or, the three cases to this problem is number of coins in drawer a > drawer b, drawer a < drawer b, or drawer a = drawer b, which we can instantly conclude that it can be brought into one drawer.

And Now The Finale

The final exams are just around the corner. Now is the time where we scramble to find our old notes hidden deep within our basements. With a bit over 2 weeks left before the final, I still haven't started preparing. But my game plan is to redo all the assignments and tutorial quizzes. This is probably what most people would do but I can't think of any other way of studying. I mean, this stuff is somewhat trivial. It's all about practice. Once you know how to efficiently create a DFSA, proof, and other stuff, it all comes down to the silly mistakes you make. Once you know how to find the area under a curve, it's a matter of whether you do some miscalculation or not.

To me, I feel pretty comfortable with the material. The only thing that is bugging me is the lack of practice problems. Though the textbook questions are helpful, I don't personally like them at all. I find them very vague compared to Danny's descriptions and reasoning. But there's nothing I can do. All that can be done is to pay a visit to the past exam repository and do as many exams as possible..

Tutorial 8 Part 2 Part A Attempt

Devise a DFSA that accepts the language of strings over f0; 1g with an odd number of  1s and and even number of 0s.   ('*' = '>')


Empty String --> A
A + 0 ---> C
A + 1 ---> E
E + 1 ---> D
D + 1 ---> E
C + 0 ---> D
D + 0 ---> C
E + 0 ---> B
B + 0 ---> E
C + 1 ---->B
B + 1 ---> C

(sorry i couldn't draw a picture.. I tried to make one text based and it turned out disgusting)

A -> empty string only
B-> odd # of 1's, odd # of 0
C-> even # of 1's, odd # of 0
D-> even # of 1's, even # of 0
E-> odd # of 1's, even # of 0 

P to the E to the Y

I just had a conversation with an upper year student who just finished is PEY and is pursuing a Specialist in Physics and Computer Science. Many interesting things popped up during the conversation, but one of them stood out from the rest; summer research.

It seems that the majority of us are just planning to finish a bachelors in Com. Sci and head out into the working force, and there is absolutely nothing wrong with that! Everyone knows that the demand for computer scientists are growing dramatically and that there will be a ton of jobs available (especially since we graduated from U of T). But there will be a point where you will be fighting to get that promotion, or that salary raise in you job. This is where your past experiences come into play. Experience indicates that you have been exposed to ___ (whatever this topic is) and worked on it to a fair degree. You instantly become more trustworthy and responsible in the eyes of whomever you're working for. This is why PEY is very important. You are basically given a change to leave your studies for a year and go into the practical applications, while being paid around 40 thousand. Not only that, you become close with your co-workers and boss', which also give amazing recommendation letters. According to the com. sci website, over 50% of the students land a permanent job at the end of PEY (whether they take it or not is not the point). In general, I feel like PEY is something everyone should try. Though I haven't given it a shot, I'm pretty confident that it is something I will not regret.

CSC236 Fall 2012 Quiz #5 (My solution)

BinSearch(A, first, last)
         if A[first] == A[last]                                   ---------------------1
                  return A[first]                                   ---------------------2
         mid = floor((first+last)/2)                        ---------------------3

         if A[mid] > A[mid + 1]                               ---------------------4
                   return BinSearch(A,first,mid)      ---------------------5
       else
                   return BinSearch[A,mid,last]       ---------------------6

Lines 1-4 will execute once, so it will be of theta(1) at max.
The rest of the code approximately runs around half times the length of n,
so we will write that as the ceiling of n/2, as we dont' want to lost any iterations
by using the floor value.

This creates


T {theta(1)                      n = 1
    theta(ceil(n/2))          n>1
    }

Then T(n) = theta(1) + Theta(ceil(n/2))
Then a = 1
Then b = 2
Then d = 0




      

Team Project Hustling

Most of us are taking CSC207 at the same time as this course. And to all of those who are, we are aware of this 4 man group project which is due within a week's time. This to me feels like the first REAL group project I had in university. Our task was to make a "program" that takes user inputs which are in the form of commands, and execute it. It's tricky, since everyones code is dependant on the others and you cannot finnish this assignment without cooperating with the others. From what I remember in High School, there is usually one person who does the majority of the work the night before the project is due and the other group members just "hang around" to ensure that the project is finished on time. Thing with this is that the TA's can check when you did work and when you updated your last entry, so essentially your TA will know if you did everything in the last minute, and who in the group did what.

I personally like this setting because it feels very much like what I would expect real group projects in the real world to be. Also, everyone in the group is actually working. It isn't one of those groups where one person is the "leader" and tells everyone else what to do. Everyone in here has a say in what's going on because everyone is at the same level. I hope most, if not all of our group projects follow this trend.

Test.. Assignment.. Test... Assignment.. Test... Exam.. It never ends!

Long time no see folks! First and foremost I'd like to apologize for the lack of uploaded posts. I was caught up in the middle of exams and assignments for the past few weeks.

So it seems that I don't know structural induction as well as I thought I did.. Every mark I lost on the term test was on the final question, which was purely a structural induction proof. It seemed to be relatively simple and straight forward when Danny covered it in class, however, it seems that there were a few points that I missed. Just because it seems simple doesn't mean that it is. I probably should have practiced structural more for the test. I didn't review structural as much as I did for the others, secretly hoping that it wouldn't come on the test... I guess there's a lesson to be learned from everything.

In other news, I'm really starting to enjoy this course. It's a nice change to approach computer science from a  different approach; dealing with the logic rather than the coding. It's a good change to go to conceptual from practical. I also came across this online source which turned out to be an excellent document to use in this course. Check it out! http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf

-Garisian Kana