Piles of Pennies Problem & Last Post

Hi!

For my problem solving episode I decided to choose the Piles of Pennies problem from the problem-solving wiki website the professor gave us. The question was:

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 can contain 48 pennies using the two following operations? Also Can you arrange things so that one of the drawers can have any number of pennies in the range [0, 64] using the two following 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 pennies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

The first step to solving this problem is understanding the problem:
In order to solve this problem I must show that I can create two piles, one of size k (where 0<=k<=64) and the other of size 64-k. First I want to show that I can create a pile where k is 48, and then I want to show that I can create a pile where k is any integer in [0, 64].
Also, note that you can only perform the operations when the respective drawers contains an even amount of pennies.

The second step to solving this problem is to devise a plan:
First, I will check that the drawer with all the pennies contains an even amount of pennies, otherwise I cannot perform any operations on it. Also the only choice I have for my first move is to split the left drawer of 64 pennies into two so that the left and right drawers have 32 pennies each.
Also after the first move, one idea is to perform the L and R operations in different combinations in order to get a drawer that will contain 48 pennies, and then continue to perform operations until we show that a drawer can contain any amount of pennies between 0 and 64 inclusive.
This problem kind of reminds me of the three jugs problem where you have 3 jugs, one of size 3, one of size 5, and one of size 8 where the size 8 one is filled fully with water and you pour the water into jugs to try to get a result where two jugs are filled with 4 liters each.
I think I should start here by trying to find a combination of operations until I get k to be 48 first. Then I will try to find a pattern if I can to solve the next part.
Also to see if k can be anything between 0 and 64 inclusive, I think constructing a tree with all possibilities would be good.

The third step is carrying out the plan:
To get k = 48. We can perform the L operation twice or perform L then R:
Left drawer: 64 Right drawer: 0
Left drawer: 32 Right drawer: 32
Left drawer: 16 Right drawer: 48
Therefore you can arrange things so that one drawer has 48 pennies.

Construct a tree (here is a picture because I was too lazy to type it):

Sorry for the mess, I'm not that skilled with the pen as you can see.

Anyways, from the picture, an arrow from the left value in the coordinate means performing the L operation and an arrow from the right value in the coordinate means performing the R operation. The left value and the right value in the coordinate represents the number of pennies in the left and right drawer, respectively.

As you can see, a drawer can contain any amount of pennies, k, where k is an integer between 0 and 64 inclusive, through the L and R operations.

Looking back:

Looking back on how I approached this problem, I feel that there are other ways to solve it. I think I took the easiest, most simple way to solve the problem, but I think there are more efficient ways of solving it. There must be a way to solve this by induction.  Although, creating tree diagrams are very effective in solving problems where you deal with combinations. In the end, you CAN arrange the pennies, through the 2 operations, so that a drawer can contain any amount of pennies between 0 and 64 inclusive.

Also, in other related news. This will be my last post for this blog. I know, it's a sad moment. Don't worry, if you want to creep my thoughts or stay in touch with me, you can follow me on twitter: @ZainManji

Overall, I really liked this course and the professor. Professor Heap made the concepts easy to understand and even interesting. I really liked how he set up the course so that tutorials involved quizzes which could help you learn how to tackle different kinds of problems with the concepts learned in lecture. They also really prepared me for the term tests. I hope to have him again/work with him later on in my university career.

Anyways,

Peace out!

Last Week!

Hey everyone!

I'm really excited for this week to begin because it's the last week of classes! Also this means that final exams are this much closer than before, but I only have 2 final exams this semester so I don't mind. This also means that the holidays are coming soon, which for me means spending time with family and friends. Anyways, I know I said that my next post would be the problem solving episode but, yet again, it's not. In the next day or two I will be posting that, out of pure procrastination. Sorry guys.
Anyways, we are learning about DFSA's and regular expressions in class these days. I actually enjoy this topic, because I like the topic. Constructing FSA's to me is sort of solving a puzzle. You have to consider all the possibilities before the construction and it's very easy to miss a possibility that will drive to DFSA to be incorrect. Also I took software design over the summer where we learned about regular expressions, so it's a familiar topic to me. I always enjoy topics which I am already familiar with because it's easier to understand. The semester is almost done which means that this blog will soon come to an end. I will give my final thoughts of the course in my last post. Also the last quiz is tomorrow, so I am hoping to end the quiz season off on a positive. I want a 2/2!

Talk to you soon.

Cheers!

Almost Done!

Hi everyone!

Recently assignment 3 has just been posted, and when I first looked at it I thought to myself: "What is this jibrish???". Seriously, if you were to show a random person on the street (assuming they have no experience in computer science), they would also think the same thing and be even more confused than I was, in tackling the assignment. However, I first looked at this assignment before even reading up on what we were actually covering in class, so that's probably why I thought it looked like jibrish. I like to start my assignments early just so I can get it out of the way, and also because I have other plans the week that it's due, that would prevent me from working on it. I never used to always start my assignments early, but since I only have 4 courses this semester and since I have a lot of free time during my weeks, I had nothing better to do than start the assignment. Haha. I'm a nerd! Kidding! Sort of...

Anyways, I just realized that there are only 2 more weeks of classes left! The semester actually just flew by so fast! Also another note, it's been 20 days since I submitted Assignment 2 and I still haven't gotten a mark back! I'm not complaining or anything, but the suspense is killing me! Also I know I said that this post would be a math problem that was difficult, but I still haven't found one yet, because I'm too smart. Haha, I'm just kidding I just can't solve any of them and it's hard to pick one. I'll get to it soon, don't worry guys. I know you're all eager to see it.

Ciao,

Happy Thanksgiving to all my American friends!

Relaxing

Hey everyone!

It's been such a relaxing week. I decided to not spend this week doing any work other than attending classes, because I was pretty tired from my midterms. This week I'll get back to work though. We're covering proving the correctness of programs right now in lectures, and I don't think it's too hard, but it will still take a bit of time to understand and settle in. We covered a bit of this topic last year in CSC165 so hopefully I will be able to pick up the concepts and methods quickly. I'm pretty sure we are getting our second midterm marks back this week, so hopefully everything goes well. This coming week, you can expect me to post a mathematical puzzle/problem I found interesting and challenging on the blog. I hope you're excited! Just kidding, I wouldn't expect you to be excited about reading about a math problem.

Aside from the course material, I'm am planning on reading up on and learning the basics of creating apps for the Android platform this week. I have a couple of ideas, very basic ideas, for apps that I want to create and hopefully distribute on Google Play. I still can't believe that some people make the simplest apps possible and generate such a large revenue from it. For example, a basic flashlight app for the android has been downloaded and paid for so many times from the app store! It just creates a bright light on the phone! Isn't that crazy!?! As you know from my last post, I'm really into sports, especially tennis and basketball, so my ideas for apps are based on sports, healthy living, and sustainability of the body. Hopefully, I can create great apps and will just become super popular on the app stores. Then I can drop out of school! Ha, just kidding.

I'll keep you guys posted on my progress!

See you later!

Almost Done

Hi everyone!

I'm not sure if anyone, other than my professor and the TAs, is actually reading this blog, but I hope you are enjoying it! This week has been hectic! I finished 3 of the 4 of my midterms with the last one being tomorrow and for this class. I can't wait to finish it and just relax, eat, sleep, workout, and just "chill". Not much has happened in regards to the class this week. Our second assignment was due Friday and we just started learning about the correctness of programs. I found the assignment actually kind of sneaky, if that makes any sense, because of the first question. The first question involved coming up with a recurrence, proving the recurrence, and explaining why it is true. It was sneaky because when unwinding the recurrence (which was the Fibonacci recurrence) , we actually need the Fibonacci recurrence to find the closed form of the recurrence. It was like inception, but with recurrences. Haha. Anyways, I thought it was kind of interesting.

I don't know if I've mentioned this yet, but I am a huge sports fan, especially when it comes to tennis and basketball. For those of you who watch, keep up, or just enjoy tennis, check this shot out by Grigor Dmitrov.

Anyways, I should start preparing for tomorrow's midterm. If you have any other cool videos (related to sports or computer science), feel free to leave them in the comment section below!

Ciao! 

Things are getting hectic!

Hey everyone!

I finally got my assignment mark back! It took so long for some of us for some reason. Other students got their mark back roughly 3-5 days before I did. It was pretty stressful waiting for the marks. Thankfully that's over and I'm happy with my mark, so everything is alright.

Aside from that, the CSC236 lectures have been alright. The material looked pretty difficult at the beginning, but I am slowly getting a grasp of things. There is definitely a huge change in difficulty from the work at the beginning of the semester to the work we are doing now. I was also a bit behind in the material because I spent one of the lectures trying to figure out the second assignment rather than actually paying attention. I'm all caught up though, so it's alright.

The past couple weeks have been so relaxing. I don't have that many hours of classes and on top of that I didn't have any test or assignments due. But now, I have a quiz tomorrow, a midterm Thursday, 2 midterms and the second assignment for this class due Friday, and then the midterm for this class the Monday after that! (You can pity me now). I'm actually kind of looking forward to this week, which may sound weird, because I like being busy. These past 2 weeks have been great, but some of the days I was pretty bored. Also, the feeling you get after finishing such a hectic week is amazing. It feels like you can just lie down and not care about anything. It's so relaxing. The sad thing is that I can't fully enjoy Halloween because of all the work coming up.

This was sent to me and it pretty much sums up my life at the moment: http://whatshouldwecallmcgill.tumblr.com/post/34358018055/not-being-able-to-fully-enjoy-halloween-because-i-have

Anyways time to get back to work! No pain no gain!

Wish me luck!

Over One Hurdle

Hey everyone!

Alright so this week was not that bad. We got our marks back for the midterm (I did well, so I'm not complaining), and we should be getting our marks back for our first assignment any day now. Apparently, someone in another timezone is marking the last question of the assignment... I don't understand why the professor just doesn't get some TA at the university to mark that last question instead of someone in another province. It doesn't really matter, but I just find it a bit weird. Maybe the person marking the last question is some sort of super genius... Hmm...

Just when I thought we would have a little break in this course, the second assignment gets assigned. I guess this is what you get once you start paying for school. Constant work. I shouldn't really be complaining since my class schedule is pretty empty.

Anyways, Halloween is coming up and I'm trying to decide on a costume. My choices right now are: Abed from Community, a Rubik's Cube, Obama (just a mask of Obama's face), or the Old Spice guy from the commercials. Hopefully, I can come up with some more ideas. If you have any ideas on what I should be, please leave a comment below. I'd appreciate it. It has to be really COOL though. I'm just kidding, it can be anything.

Alright, well it's Friday night so that means it's fiesta time!