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.