Problem Solving: Penny Piles

Unlike my recent posts, the title of this post will not start with "Week in Review." (I couldn't think of any better titles for my weekly posts.) I'll be writing about a problem solving exercise that our class did yesterday, called "Penny Piles."

The four steps to problem solving by Polya are:

1. Understand the Problem
2. Devise a Plan
3. Carry Out the Plan
4. Look Back

Using this approach, I'll explain how to solve this problem.

1. There are two drawers. One of the drawers is filled with 64 pennies, while the other one is empty. The question here is: Can things be arranged so that one of the two drawers has 48 pennies? This is where two operations are introduced: l and r.
• l: If the left drawer has an even number of pennies, half of that amount can be transferred to the right drawer. This operation will not work if the number of pennies on the left drawer is odd.
• r: If the right drawer has an even number of pennies, half of them can be transferred to the left. Once again, this will not work for odd amounts.
2. The plan is to consider the range [0, 64]. The goal is to arrange the pennies so that one of the two drawers has 48 pennies as well as another number within the range using the operations l and r from the previous step. To achieve this goal, a number of different possibilities can be mapped out in various ways.
3. At the start, the left drawer has 64 and the right drawer has 0. To execute the plan, half of the pennies in the left (32) can be transferred to the right using operator l. Now it's even. Both drawers have 32 pennies each. But one of the drawers must contain 48 pennies as per our problem. Operators l or r can be used in this case because 32 is an even number and the pennies are divided evenly. For example, if we transfer half of the pennies in the left drawer to the right, the result is 16 pennies in the left and 48 in the right. Therefore, it is possible for one of the drawers to have 48 pennies using arrangements, but the sequences are endless. Here is an example sequence using the l operator: 
• Start (left, right): 64, 0
• 32, 32
• 16, 48
• 8, 56
• 4, 60
• 2, 62
• Finish: 1, 63
4. To check the result, a tree diagram can be drawn, listing all the possibilities. Another way (similar to my approach) is to create an output sequence using only operators l, r, or a combination of both. Using an equation to derive the solution may also come in handy; for example, x + y = 64, where x and y represent pennies in the left and right drawers adding up to 64, respectively. To conclude, any number in the range [0, 64] can be achieved. 

A (Short) Week in Review: More proofs and midterm results

This is the fourth "Week in Review."

This week was short due to Thanksgiving on Monday. Thus, there were no tutorials and only two lectures.

Unfortunately, I haven't had time to get my test, but my test score wasn't that great. I did pass, so that's something to be happy about, I guess? However, Professor Heap announced in lecture that the class average was in the low 80's. That's amazing! I thought. My test mark is way below the class average. I messed up the first question really badly when I thought I'd do well on it. I didn't do so well on the last question either. That's okay; I'll do better on the next test. But the feeling of getting a mark that is below the class average makes me feel defeated. I'll approach Prof. Heap on Wednesday during office hours to see where I went wrong and move forward. I might be upset temporarily, but I have to keep in mind that this was the first test and that I should still be happy because I passed.

I'll have to admit that I didn't study hard enough. I had my psychology test the very next day and I was a bit too focused on trying to memorize as much as I could because psychology involves memorization of terms. I did study some of the material, though. I still managed to get an adequate result despite my lack of study.

This week was a continuation of proof writing, all with the same proof structure:

Assume...

(insert "Then" statements here with proper indentation)

Conclude....

We've been looking at proofs for about a week now. More specifically, we've looked at certain kinds of proofs.

Recently, we've learned how to prove using different cases. Sometimes, a statement can have different possibilities. If this is the case, it is best to split the argument into multiple cases. For example, we can consider the cases when a number is odd and a number is even. We can integrate this into our proof after we have made our assumption.

The floor function was introduced. The "floor of x" is the largest integer that is either less than or equal to x. On a graph, it looks like this:

This concept is seen once again in MAT137 on a practice problem set, which is used to help students prepare for Wednesday's test.

Proofs can be time-consuming to write. In CSC165, we use a proof structure that mostly involves the written word, especially Python-style comments on the side (beginning with "#") as seen in CSC108. In MAT137, I start with my rough work and then carry on with the proof, but I also have to use words. For my problem sets, I lose marks if I do not explain my proof in words.

I often comment on the similarity between CSC165 and MAT137 because I have both on the same days and they complement each other very well. Technically, CSC165 is a computer science course, but it's all about math and logic. Using what I've learned in 165 can help me with the material presented in 137, notably the logic component. 

Week in Review #3: my first midterm for university

Yesterday morning, I had my first ever midterm test for university. Before the test, I went over all the concepts we've learned up to Week 4. I made study notes, redid my quizzes, and revisited the assignment sample solutions. I looked at a past test from 2013, which seemed to help a bit. I also went to the Computer Science Help Centre at the Bahen Centre to study with friends and ask a TA questions. I should go there for help as well, seeing that it's an excellent and free resource. However, I'm not gonna lie when I say that I did feel very nervous. I hope that my preparation was sufficient in order to do well on this test. My class was even allowed to bring a study sheet.

As I saw the test, I read over it. Some questions were obvious to me; some, well, not so much. Things like negation, true/false, and sets were involved. It wasn't an easy test. The good part is that I was able to finish the test within the fifty minute time frame without leaving any blanks. The not-so-good part is that I don't know how I feel I did on the test. I don't know if I did well or failed it. I'm a bit worried, but I shouldn't be too, too worried because there's another midterm next month followed by the final exam in December. Professor Heap will weigh the two accordingly; the better of the two will be worth 10% while the other is worth 6%. That's not bad.

On a positive note, I'm glad I got the midterm over with.

Aside from the midterm, I had my weekly Tuesday morning tutorial. We went over proof structures, for which we would be quizzed on at the end of the period. It went well aside from the fact that it started to rain when I got out of the subway.

I seem to have a better understanding of proofs now that we went over them in tutorial and in lecture, where we used the examples on the slides. I will use what I've learned in CSC165 to help me write proofs for my upcoming MAT137 midterm. Those two courses make an excellent combo.

Week in Review #2: Prove it!

We went over the proof outline this week. This outline helps us write good proofs that are clear and organized. I have seen this already in MAT137, but given the similarity between that and CSC165, it came back to me.

First off, a proof is the explanation of why and how a statement is true. To prove something, we have to believe that the statement is true. We start by understanding why it's true. Once we understand why it's true, we then go on to writing it down. However, it does not stop there. Proof writing is not a finite process. Sometimes we may encounter gaps that need to be fixed that require us to start over. The first step, understanding the proof, is where we try and strengthen our weak spots. In MAT137, we call this "scratch work" or "rough work." It is a messy process, but it is necessary that we go through this process to strengthen any given proof. Much like English writing, there is an audience to our proofs: CSC165 students and staff. We have to make sure that our audience can understand our proofs. 

As for style, indentation is required to show scope of assumption. We also begin our sentences with words such as "Assume" and "Then" throughout our proofs. As I learned in MAT137, I could also end a proof with ∎.

This is how a proof would generally look like. We start with "Assume" and end with a concluding statement (starting with "Then" or "Conclude"):

Assume...

      Assume...

      Then...

      .

      .

      .

      Then....

Then...

In addition, I had my third quiz in tutorial on Tuesday. When I went over the exercise with the TA, I had a better understanding of the material. The quiz wasn't so hard either.

I also had my first assignment due yesterday. At first, I did not know how to approach many of the questions. I worked with other people to get help. After many hours, it was finally finished. I felt a sense of accomplishment and relief.