Problem Solving: Penny Piles

A while ago we were presented with the problem-solving handout "Penny Piles".

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 combinations of the following two operations, l and r?
l: If the left drawer has an even number of pennies, you may transfer half of them to the right drawer. If the left drawer has an odd number of pennies, operation l is disallowed.
r: If the right drawer has an even number of pennies, you may transfer half of them to the left drawer. If the right drawer has an odd number of pennies, operation r is disallowed.

The Plan:

For this first problem of 48 pennies, the plan can be simply trial and error because this does not take many steps to achieve. 

Carrying it out:

We will start by having 64 pennies first in the left drawer and none in the right.

 L                R

64                0

Then we transfer half of 64, which is 32, to the right drawer because the left drawer has an even number of pennies and this operation is allowed.

 L                R

32               32

Then we transfer half from the right drawer, which is 16, to the left drawer, and the result will be our solution, as 16 + 32 = 48

 L                R

48               16

Now, the second part:

Choose another number in the range [0,64]. Starting from the same initial position, can you arrange things so that one of the drawers has that number of pennies? Are there any numbers in that range that are impossible to achieve?

The Plan:

A good approach is to work backwards. This means starting with our desired result in one of the drawers, and the other HAS to be the amount for the total to add up to 64 pennies. Then, with each step we will double the amount instead of halving it. 

Carrying it out:

Lets choose the number 17.

 L                R

17               47

We double what the amount of the left drawer has because each step requires us to half the previous amount.

 L                R

34               30

This time we double the right drawer because 34 * 2 is 68, which is not possible (we only have 64 pennies).

 L                R

 4                60

 8                56

16               48

32               32 

64                0

What about just 1 penny?

 L                R

 1                63

 2                62

 4                60

 :                  :

(steps we already done in the previous example)

There are actually no penny values that are impossible to achieve in the range [0, 64]. Which means that all natural numbers from 0 to 64 are attainable from these penny arrangements. 

Here's a good blog post I found on the same problem: http://juliaslog.wordpress.com/2014/10/27/a-series-of-unfortunately-inconclusive-events/

Countability, Assignment 3, and Final Exam

After learning computability and impossible algorithms like halt, we moved onto the topic of countability. When we count, we automatically start off like "1... 2... 3..." and etc. So "counting" is actually just enumerating the natural numbers. So, we say the set N is countable, and any set A that satisfies |A| ≤ N is countable as well. So, the set of integers is countable, and, to my surprise, the set of rational numbers (Q) is countable as well (using diagonalization). Moreover, we learned that infinite sets does not necessarily have the same size. However, if two sets (finite or infinite) can be matched up 1-1 and onto, then they have the same size. 

Assignment 3 is due tomorrow at night. I am still working on it and I am going to office hours tomorrow to get help. With that being said, the Final is in 10 days and I need to start studying my butt off. 

Big-O for General Statements and Computability

Fall break was last Monday and Tuesday and I definitely still do not feel 100% in the zone. I had fun for my long weekend and it's just dreadful thinking about school work again.

For last week's lectures, we discussed about Big-Oh applying to general statements, where a set of functions is not growing faster than another set. These are proven roughly the same way as specific functions, but different in the way that there can be more than one c and B now (which we label B' or B sub f, etc). Also there can be disproofs as well as proofs, such as
f ∈ O (1/n)  ⇒ f ∈ O (1/n²) for example is not true. 

We're also learning computability and why some problems cannot be coded. Some questions look easy to compute, but in actuality there exists no algorithm for it. In fact, the halt(f, n) function is one that is impossible to write, and it can be proven by contradiction. Halt's purpose is to detect whether or not a program stops or goes into an infinite loop somewhere along the line. However, if the program goes into an infinite loop, a response is never reached by halt, therefore it is not computable.

Assignment 3 has also been posted and I really don't want to start on it..

Big-Oh/Omega/Theta

We're learning more about Big-Oh and its proofs. With these proofs, I think it's not hard to follow through with a bit more practice. However, it was in the previous lessons with analysing algorithms and counting steps that confused me most. Seeing the sigma and all these other complicated notation was really frightening and I think I will need more clarification on that part.

I have been learning a lot from Instructor Larry Zhang's lecture slides and I think his notes are very helpful and easy to comprehend.

Big-Oh's definition is that if a function a is in the Big-Oh of another function, b, it simply means that cb will grow faster than a after a certain point, and cb will become the upper bound of a, where c is a wisely chosen constant.

For a f(n) in O(n²) the formal definition is
∃c ϵ R⁺, ∃B ϵ N, ∀n ϵ N, n ≥ B ⇒ f(n) ≤ cn²
For Big-Oh proofs, the structure starts off all very similarly. Choose a c and a B and make sure it works with n. For more complex proofs, such as higher degree polynomials, we overestimate the left and underestimate the right. For non-polynomial functions such as 2^n, we have to use the definition of a limit to prove Big-Oh.

Big-Omega is the reverse of Big-Oh. It's saying that there is a lower bound cb to a. We now have to pick a c small enough to make the right side a lower bound.

Then we have general statements about Big-Oh. We're now proving the case for a set of functions. For example, in Wednesday's lecture, we touched on proving the statement
∀ f, g, h ϵ F, (f ϵ O(g) Λ g ϵ O(h)) ⇒ f ϵ O(h)

Post Test 2

Let me just say that I had a 2000 word essay to write that was due the day Test 2 was written too, so I have justification for not studying a lot.

I bet you can guess where this is going - the test did not go well. For the first question, although there were (existential quantifiers), the whole thing was being applied to a  (universal)... So instead of proving it for all, I proved it for a specific case. Probably not going to get a lot of marks on that.

Then the 2nd and 3rd questions were just... yeah. I did still write a basic structure for them but I just couldn't figure number 2 out. I think I really need to focus and study more for 165. It's just this specific case where I slacked and now this is the consequence. I also didn't know we were still allowed aid sheets!! I felt so dumb because I thought they were only for Test 1...

But yeah that's Test 2. Hopefully I still passed. Not looking forward to next topic because it's super confusing so far (Big O).

HAPPY HALLOWEEN

We have another assignment and term test next week... kill me now. Next week is actually so busy I don't want to deal with anything, especially with all these Halloween events coming up. I just want some time to relax and have fun.

Anyways in Monday and Wednesday's lectures we talked about "Worst Case" and "Big-Oh"... and it's SUPER confusing. I didn't understand what was happening at all. Basically we were given a python function and we figure out a algorithm runtime and go through "asymptotic analysis". Very confusing stuff.. Like, I couldn't follow at all. I hope they post a sample test for Term Test.

Proofs

In the past two weeks we have been working on proofs in CSC165. It is important when writing a proof that there is an organized structure, and we have been taught very thoroughly how to approach a proof and what structure is used. To begin with, assume the domain, then assume antecedent, then we go through to prove that the antecedent does conclude the consequent, then we end with the concluding the universal quantifiers. So far we have done proof by negation, contrapositive, contradiction, uniqueness, and cases. There are a huge variety of proofs and their strategies are all different. I think through practice, it is not hard to achieve a good mark on the next term test.

Still in test season

CSC108's midterm was just yesterday and I don't think I did well on that. I ran out of time for the last question and I didn't know how to do it to begin with... the test was more challenging than I expected. I also wrote another midterm today, in East Asian Studies - so, lots of tests lately. The last one for the time being is MAT137, which is next Wednesday. I have been really stressed out lately, and I'm considering the possibility of dropping courses..

Anyway, transitioning to something more on topic, we are currently learning proofs in CSC165. Proofs have a certain structure and format that should be followed when writing one. I think I can get the idea. Again, I just feel overwhelmed by the amount of things happening right now.

Got past Test 1

That's one out of the way... Only three more to go.

The term test turned out much better than I thought. I was really nervous for it and crammed a lot the night prior but it was actually quite easy. Looking through past notes and the sample test helped a lot and I found a lot of the concepts more comfortable than before. Although, questions that involved python language were a bit of a struggle - but good thing we were allowed an aid sheet (LOL). What I'm worried about now are my other upcoming tests. I feel like everything is so rushed and it's a bit overwhelming, especially MAT137. I really hope I don't fail any courses. God. University's so hard.

Test incoming

After finishing Assignment I this week, we are greeted with the first term test in the week ahead. I don't exactly know my grasp on this course. Some areas I'm like: "yeah, I follow," but then when I need to apply the knowledge, I feel like my understanding is vague. I have a hard time with Venn diagrams, where to put a check mark or an X, and also putting sentences into symbols. I'm going to study this afternoon by trying to go over lecture notes and also getting help from online. A lot of the material in CSC165 is similar to MAT137, and that kind of makes it a double edged sword. If you get the concepts, you're good to go in both courses... On the other hand, if you struggle with it, you won't do well in either. Hopefully by going over the notes in CSC165 I will also improve in MAT137.

Week Three

This week's topics were easier to comprehend, but still confusing at certain parts. I have yet gone to the CS Course Help Centre but I think I will some time next week.
The questions assigned for tutorial got progressively harder as we went through each problem. By the end of the first question, the conditions were difficult to satisfy and it is crucial to pay attention to details like plural versus a single object. Also, translating english into symbols is always more complex than the other way around. I need to practice in these areas I struggle on but I don't know how to get practice. Just assignments and quizzes aren't enough to improve my understanding and skill. I hope after the first assignment I will have a thorough grasp on the material.

First SLOG

This week in CSC165, we discussed many new topics including quantifiers, sentences, and implications. To be honest, a lot of this material is somewhat challenging to me. The main reason, I believe, is the new lifestyle college students have to adapt to in terms of time management and independency. Coming out of high school, we are so use to relying on the teacher or our parents. Now in university, a whole new responsibility is given to us, and it will take time to accommodate to the changes. However, I do enjoy the class so far because Professor Heap is an interesting lecturer and makes concepts easier to understand. Some topics that made me struggle includes quantifiers and implications. I plan to break it down in detail on my own time to get a better understanding. I hope to become more confident and comfortable with the course throughout the semester.