Week 9

I wasn't here this week for the midterm on Monday, so I wrote the midterm on Thursday instead. The midterm was not what I expected whatsoever, and I was not prepared for the material that it covered. Since I wrote the evening section's midterm, I expected the evening section to cover similar material as the morning section at the same pace, however, the midterm covered material that was ahead of what the day section midterm was supposed to cover. So once again, I don't think I will do too well on this midterm.

The reason I missed class was because I flew out to Seattle to due several interviews for a summer internship. I got the internship so now I have no regrets about missing class. I also missed lecture on Friday, and when I look over the notes from the day section's class, they were not very descriptive. So I think I'm going to study the evening section's notes for this week.

This week we learned proving partial correctness of an algorithm that determines an nth power of an integer. Really all that this involves is proving the loop invariant, but in most cases we must determine this loop invariant by tracing through the algorithm and noticing what is consistent at the end of every iteration of the loop in the algorithm.

I also look at the problems that Professor Heap posted on his problem solving wiki, and I think I will solve the Penny Piles problem. Here is the 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 pennies  transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

What about arranging things so that one of the piles has other numbers in the range [0,64]? What about starting with a different number of pennies in the left drawer?

You may record your problem-solving excursion below the horizontal line.

My intuition tells me that it is impossible to achieve odd numbers of pennies in either drawer, except for 1 penny in one drawer and 63 pennies in the other, since 64 is a power of 2 and you can only divide by 2 if the drawer contains an even number of pennies. I will think some more about this problem, and I will start the problem-solving excursion this week.