Week 8 - Oh no we still have to do proofs?? + Problem Solving Wiki

All along I've been hoping to stray away from proofs and start going through programming algorithms, but of-course, they had to combine both. This week we mainly worked on algorithm analysis. We went through what upper bound O(n^2) and lower bound Omega(n^2) means in analyzing an algorithm. Upper-bound is limit which the actual run time of the program will never be larger than, and lower-bound is the opposite, which the program will run the fastest. What I found was surprising was that you don't need to define the function's speed, but you're allowed to over-estimate when solving for the upper-bound and underestimate for lower-bound. However, I find it difficult to understand

PROBLEM SOLVING. Penny piles!
There are two drawers, the left drawer has 64 pennies, the right drawer contains zero. Is it possible to make it so that one drawer has 48 pennies by transferring half of one pile to the other (You cannot transfer the pennies if there are an odd number of them in one drawer)?

Working as a group, we all tried our best to understand the problem as much as we could. We drew a tree diagram to help us illustrate the possible answers. We first saw that it was possible to make one drawer contain 48 pennies through trial on paper. However, how could we prove that you can make any number from 0-64?

We continued to seek an algorithm between different criteria of numbers. We tried odd numbers, even numbers, prime numbers, and through the analysis of the steps we used, we found a pattern. Instead of seeking a specific number, we should instead consider the specific number and its pair that is used to generate 64. For example, if we look at the number 63, we see that the other drawer must have 1 penny. The only possible way to obtain this combination is if a drawer of 2 pennies were halved. Therefore the next combination is 2, 62. Using the same method of backtracking, we would see the next combination would be (4,60), then (8,56), then (16,48), then (32,32), which leads us to the beginning. Using the algorithm of doubling the smaller number, we found that any number from 0-64. This is because any odd number doubled would result in an even number which belong in the tree of combinations of pennies that are based on the power of 2.

Now the question is, what if you started with a different number of coins? Well odd numbers would not work as you cannot split the odd number of pennies apart. Furthermore, the starting number must be a power of 2, otherwise at some point of the algorithm, you will not be able to continue to the last number. Therefore any number with a power of 2 would allow you to make any number from 0 to that number., eg. 8, you can make any number from 0-8. This was solved through trials and error of different sums. First, 100 was tried, however it would be impossible as the third step of the algorithm would be (75, 25). Then, without trial, we saw that starting with an odd number would not work as you're stopped at step 1. Looking back at why 64 worked, it was because of its treemap that has encompasses all the powers of 2, and due to the algorithm of halving the number of pennies, you can always connect to that original treemap to lead back to the start. If I had more experience with Python and if I was less busy, I could try to make a program to simulate all the possible numbers from 0-64 to confirm the findings. Nonetheless, this was a fantastic problem exercise and quite enjoyable to solve. That's all for this week, hopefully I am ready for the test next week. Wish me luck (I still have trouble remembering these damn proof structures! But at least I have the cheat sheet!)