Officially, CSC165 ended just last night, but I forgot to make my final post so I am doing it now.
Assignment #3 was pretty much like assignment #2, where you had to prove or disprove several mathematical statements. Compared to #2, #3 was actually even a bit easier, because there were less questions in #3 and also because the structure of the proof was essentially the same as the ones we mastered in the previous unit, except it was applied to different types of problems. The last question was the only part that was troublesome to figure out, but it turned out that the correct way to do the problem was just to literally follow the proof structure shown in the course note. BUT MAN WAS THE COURSE NOTE CONFUSING! I had to go to a help session and a tutorial to clear up the problem, but even then I was still confused whether the solution for the last question was really correct. Well since I already submitted the assignment, it is too late to contemplate it now.
Several people gave me comments about this course before I signed up for it. They warned me that this course is a "homework hell", that "professor don't teach the course well", or that "only smart people can do well". Oh how wrong I was. It turned out that the professor was nice, assignments were straightforward, tests were easy, and the whole course is kind of relaxing. And this blog. This is definitely the most unorthodox academic evaluation I have ever had, but whoever came up with this idea needs to be praised, because having a chance to look at other people's blogs and replying immediately back to the comments of my own blog were definitely something that I enjoyed doing. Overall, I am 100% glad that I took this course at this time of the year. I was lucky enough to meet a professor who can make the students enjoy the course while successfully teach the students computer theory.
Lastly, thanks to all of you who were reading my blog since January. Perhaps in the future (maybe in the second year computer theory course), we might meet face to face. My actual name is not Suzushiro in case you don't know. But if you ever see an Asian guy who is a fourth year life science taking computer science course starting September of 2013, then that would be me, and feel free to say hi to me when you see me.
Well, that ends my last post in CSC165. Take care and goodbye to y'all.
Saturday, 6 April 2013
Tuesday, 2 April 2013
Who wouldn't want free lunch?
As part of the course requirement, I need to write about an episode where I solve a math problem and show the steps I took to solve it on this blog. The one I chose is this one here:
I chose this particular problem because it was really easy to understand and because I got hooked by its title. I mean, who wouldn't want free lunch?
[From here, I am going to assume you read the problem and know what I will talk about. It shouldn't take you more than a minute to understand what the problem is about]
Looking for a pattern for who wins was the first thing I did, because it is the easiest and fastest way to come up with a solution. So I set up three groups of friends with sizes of eight, nine, and ten. I found that f1, f3, and f5 got free lunch when their group sizes were eight, nine, and ten respectively. Subsequently, I found that when the group size is eleven, f7 won. So clearly, there is a pattern where f(y = 2(x-7.5)) is going to get a free lunch if the group size is eight or above. But I wondered, who is going to win if the group size is less than eight, could it be f(-1)? To see who wins when the group size is less than eight, I first looked for who wins when the group size is seven, six, and five, and I found that f7, f5, and f3 won respectively. So without investigating the result of who will win when the group sizes are one, two, three, and four, from the pattern above, I know that f1, f1, f3, and f1 are going to win respectively.
From the analysis above, I figured out the fundamental behavior of who the winner is going to be. Basically, the winner ID is going to increase by two from one until the winner ID is equal to the group size. After that point, the winner ID is going to start from one again, until it once again reaches the group size by increasing the winner ID by two every time the group size increase by one. The problem now is, whether I can find a function that can accurately portray this scenario.
In a sense, this problem is a 3-dimensional problem, because the end result (the free-lunch winner ID) is dependent on two factors, one being the group size, and the other being the number of times the winner ID had to refresh itself to f1. Therefore, if there is an equation that can determine who will get free lunch, it will look something like:
winner ID = 2n + (something affected by refresh#) where n = group size
The 2n comes from the fact that winner ID increases by two for every increase in group size if the winner ID is not refreshing. To look for how refresh# affects the stuff inside the bracket, I once again looked for a pattern in the refreshing behavior of winner ID. What I noticed was that the group sizes at which the winner ID gets refreshed at were 1, 2, 4, 8, 16, 32.........For most people, this should already ring a bell that this is a base 2 exponential function. I also noticed, that before winner ID is refreshed, the stuffs inside the bracket is a constant. In fact, I determined previously that the constant inside the bracket take a list of values -1, -3, -7, -15........ which value to take on depends on how many times the winner ID was refreshed. So now, what I am interested in finding is a function whose output is only dependent on which integer power of 2 the input is. The only one I can think of is the ceil(base_2_log(n)). With this function, I can create another function that will give me an output that corresponds to the values in the list [-1, -3, -7, -15........] based on the group size. The function that I came up with is:
1-2^ceil((base_2_log n+1)) where n = group size
Now, let's confirm whether this function can give me those values in the list. If the group size is 1, then this function will give you -1. If the group size is 2, this function will give you -3. If the group size is 3, this function will STILL give you -3. If the group size is 23 or 29, the function will give you -31. Now we have confirmed that this is the function we want to put inside that bracket to solve for winner ID. The final function that will yield the winner ID is:
winner ID = 2n + 1 - 2^ceil((base_2_log n+1)) where n = group size
or to make it sound simpler:
number of people in between you and starting person counting counter clockwise
= 2n - 1 - 2^ceil((base_2_log n+1)) where n = group size
Thus this concludes my attempt to find a way to get free lunch for whoever lucky enough to have a group of friends who are peculiar as the friends mentioned in the problem. Just make sure you know how many people are in your group, then you can plug that number into this formula, and it will tell you how many people should be in between you and the starting person.
If your friends choose who gets free lunch by counting 3 rather than counting odd, then I can only guess that the final formula look something like:
winner ID = 3n + 1 - 3^ceil((base_3_log n+1)) where n = group size
Just to make sure I was right, I plugged in n = 9 into this equation, and I got 1 as the winner ID. Then I simulated the physical scenario on paper for group size 9, and that also showed that f1 will win.
Subscribe to:
Posts (Atom)