Piles of Pennies

Continuing on from proving or disproving whether functions are upper or lower bounded by other functions, the lectures from the past week have been adding on to such proofs by the introduction of additional implications. Now statements such as those claiming that a function upper bounded by another function implies that a function squared is also upper bounded by the other function squared.

This concept brought back many previously used techniques both from CSC165 and Calculus in order to proceed with proving or disproving the statements. Overall, due to not being completely new material, my understanding of this material is not too bad. It is very similar to proofs done in the past where there are some steps acting as hurdles but everything works, as said by Professor Heap, after one special step due to the inward falling domino structure of the proofs. Assignment #3 should provide sufficient practice on the concept of proofs relating to bounds.

I have also been working on the Penny Pile problem brought up during a lecture. As of now I have not been able to formulate a solution which can easily determine whether a certain result is possible however I have put together a simple Python program to run tests to determine whether a result is possible. The algorithm used may contain some errors at this point, but they will be ironed out as progress on this problem continues.

First of all, let's go over the algorithm I had in mind when constructing this program. Writing down your ideas is always a good way to find mistakes.

1. While the goal has not been reached:
1. Check if either the left or right pile are even numbers. If not, break simulation.
2. If the goal can be reached by moving half of the left pile to the right pile, do so.
3. Else if the goal can be reached by moving half of the right pile to the left pile, do so.
4. Else if the left pile is even, move half of it to the right pile.
5. Else if the right pile is even, move half of it to the left pile.

In the coming week, this algorithm will be tested slowly using smaller sets and comparing its results to ones found by hand. The above algorithm translated into Python, in a very rough stage, is the following:



def penny_piles(goal, left=64, right=0):

    n = 0

    failed = False

    print('Left: ' + str(left) + " Right: " + str(right))

    while not(left == goal or right == goal):

        time.sleep(1)                    

        if not(left % 2 == 0 or right % 2 == 0):

            print("Failed.")

            failed = True

            break

        print('Left: ' + str(left) + " Right: " + str(right))

        if right + left // 2 == goal or left // 2 == goal:            

            left = left // 2

            right += left

            print('Adding ' + str(left) + ' to right pile.')

        elif left + right // 2 == goal or right // 2 == goal:            

            right = right // 2

            left += right

            print('Adding ' + str(right) + ' to left pile.')

        elif left % 2 == 0:

            left = left // 2

            right += left

            print('Adding ' + str(left) + ' to right pile.')

        elif right % 2 == 0:

            right = right // 2

            left += right

            print('Adding ' + str(right) + ' to left pile.')

        n += 1

    print('Left: ' + str(left) + " Right: " + str(right))

    if not failed:

        print('Goal reached after ' + str(n) + ' swaps.')

This is a very interesting problem, looking forward to working through, and hopefully solving, it.

So, the marks are here...

The results for both the second assignment and test have been uploaded to CDF. I was very happy with the test result but not so much for the assignment. The assignment was very fair and not too hard but bad time management led to this result. I was not expecting to run into some troubles with LaTeX so I left typing up and finalizing to the last few hours. I should really be more careful and plan ahead when it comes to these kind of technical details.

The main focus in CSC165 has been on algorithm analysis and proving if an equation is within the lower or upper bounds of another. I was quite confused at first but the tutorial has helped to improve my understanding. I still get stuck at times when trying to reintroduce negative terms but I am confident that this can be resolved by going over the annotated slides a couple more times. I wish that the annotated slides for the previous week were available before the test but it is no big deal. The course notes helped to combat this issue.

I have been working on the penny piles problem and am able to determine whether a certain combination is possible regardless of the number of pennies through the use of a simple python program. However, no real pattern has been found as of yet.

Prove or Disprove: Test #2 went well.

I have always enjoyed reading through and working on proofs but have never been very good at them. It is always interesting to see the why behind every what. Simply knowing what is true or false is not good enough for me, I like to know why.

For this reason, I have been enjoying the lectures even more because we are working on the topic of proofs. There have been struggles along the way but after some time spent practicing and reading over past proofs, general strategies have been developed. While these strategies are not algorithms that will work with all proofs, they are similar to the proof structure as in they make up the bulk of the proof and leave you with blanks to fill in.

Many of these strategies are common sense or obvious but having actually thought and making them precise, they make the proof process much more straight forward. One strategy that originated from working on the second assignment is as follows: When possible, always refer back to the definitions relevant to your problem. This is a basic strategy that almost anyone will know to do but having it written down and thought out ensures that it is kept in mind. Writing it down acts similarly to a cheat sheet, it is there when you need it but you do not tend to use it during the test. The cheat sheet does not directly aid individuals but it is the process of creating one that does.

I'm happy to see that a cheat sheet is allowed for the second test. As mentioned in a previous blog post, the cheat sheet for the first test was not used during the test but it still helped to create one. For this reason I will be sure to have one ready for this week's upcoming test. I will include items relevant to the strategies mentioned above meaning items such as definitions, rules, and maybe, however unlikely, past proofs that may prove to be useful.

After the test we'll be able to prove, by example, if the test went well or not.

Prove or Disprove

The second assignment's deadline is creeping up. This assignment is full of proofs which are my weakest point in this course so far. Fortunately Professor Heap spent additional time to slowly go over more proofs which greatly helped to increase my understanding on how to approach proofs.

As far as structuring the proofs goes, I have it nailed down. It is mostly a mechanical process as when you figure out which statement or assumption is associated with each symbol in the statement, it is easy to come up with the structure. The assignment handout does claim to give out substantial marks even if you only provide the proof structures meaning that even if the proofs are not completely correct, it will not be for naught. However, if the incorrect stance is chosen (true or false), no marks will be provided.

The main problem I am having with proofs is actually putting your thoughts down into non-ambiguous statements. In my head I am able to tell if the statement is true or false and even come up with examples as to why. However, I am unable to properly put my thoughts down on paper. Improving on a concept such as proofs takes time and commitment. Therefore, I am hoping by the end of this assignment I have a fair grasp on projecting my thoughts into a written format. Besides, that is the point of this course.