Wrapping Up

This blog post will be the final post in this blog. I was skeptical to the use of blogging about CSC165 but in the end it did have a positive effect. Writing is something I already enjoy doing and putting my thoughts and problems into words helped to create plans to tackle these problems head on. It was a pleasure to learn CSC165 under Professor Heap, who is, without a doubt, the best Professor thus far in my university experience. Hoping to learn under him again in the upcoming years! Last week's blog post went over the Penny Piles problem. My initial approach was to construct a program, as seen in the previous post, but after some testing this program was found to be faulty. For example, it would return that it was not possible to reach a pile with only 1 penny. However, consider the following approach, going backwards:

1 63 

2 62 

4 60 

8 56 

16 48 

32 32

64 0

Simply always moving half over to the right pile allows you to reach one. This one counter example causes my program to not be a viable solution. Let's take a look at the problem using a systematic approach, Polya's approach:

Understand the Problem

This problem forces the solver to determine whether it is possible to reach a certain amount in one drawer from a given starting point. On each of the drawers, the following operations may be employed: L: Iff the left drawer has an even number of pennies, you may transfer half of them to the right drawer. R: Iff the right drawer has an even number of pennies, you may transfer half of them to the left drawer.

Devise a Plan

The first idea was to construct a program that can simulate and determine whether scenarios can be reached. As seen in past weeks blog, a program was created but as disproved above, it is not functional. My next option was to run some manual simulations and try and find a pattern. A tree can be created showing all the possible outcomes with the following starting drawers [64, 0].

Carry Out the Plan

The following is a tree constructed starting with drawers [64, 0]:

64
32 32
16 48
40 24 8 56
20 44 52 12 4 60 36 28
10 54 42 22 26 38 6 58 2 62 34 30 18 46 50 14
5 59 27 37 11 53 21 43 13 51 19 45 3 61 29 35 1 63 33 31 17 47 49 15 9 55 23 41 25 39 7 57

Due to formatting issues, the tree is presented left to right. However, this is enough for our needs as we are only worried about whether each tree node is there. If we look through this tree, every value from the range 0 to 64 is present. Anything more than 64 is not reachable only because we only started with 64 pennies, it's not possible to just create more pennies. If you know how, let me know.

Using the hint given on the problem handout, working backwards, we can see the cause of this. This is due to every number being able to be represented in binary or with multiple additions of 2^n, n \in N.

Take for example the number 13:

13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1 = 13

Conclusion

In conclusion, since we are relying on if a number can be represented in binary, it can be concluded that ANY number can be created when dividing piles with an even number. The only time this is not possible would be when the starting piles are both odd and no operations can be carried out.

It was a pleasure to write these blogs and learn under Professor Heap and TA Lala. I learned a lot and this knowledge will defiantly come into use in my future classes and career. Let's hope second year's professors and classes are as enjoyable as this one. :)

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.

Results are in!

Both the assignment and test have been marked and returned. Fortunately I was pleased with the grades of both. They were both marked fairly and all questions were relevant to the given material, no surprises, which was nice. A cheat sheet was allowed, and I prepared one, for the test but did not need to use it at all. The greatest part of the being allowed a cheat sheet is the process to preparing one. When writing out the cheat sheet, by hand, you are forced to sit down and figure out what is important. After writing it all done in a precise and neat manner, the information just stays in your head. The cheat sheet functions as more of a tool to learn than one to aid yourself during the test.

Last week I blogged about difficulties when it comes to proofs. Fortunately this is becoming more and more clear due to continuous examples both in the lectures and tutorials. The tutorial exercises are a great way to increase your understanding and improve your speed on lecture material. Definitely something that should not be forgotten.

After working on more proof problems, reading through course notes, online websites, and aid provided during the tutorial, proofs are not so foreign anymore. The proof structure has been described in a great manner by Professor Heap: Like dominoes falling inwards. Simply complete one step from both sides and you are eventually left with some blanks to fill in. Unfortunately there is no one set plan to get past this final hurdle but a lot of the work has been done and the groundwork has been lain if the proof structure is applied. I will continue to practice proving more statements in hope of improving my speed to fill in the blanks.

There was one slight problem with my test where the answer that I had crossed out was marked instead of the one I meant to be marked. Due to limited time, I was not able to erase my incorrect answer and simply created a new box and wrote the correct answer in that area. After doing so, the old answer was crossed out. The line may have been too faint which led to a TA marking my old answer. Immediately after spotting this error, I took some pictures as proof (best I could do) and emailed the Professor as soon as possible. Hopefully after taking a look at the test, Professor Heap is able to resolve this issue. If not, I'd better get used to crossing out answers in a more obvious fashion.

Tests off the horizon... for now.

The past week has been focused on preparing for the term test not only for CSC165 but for other classes as well. Fortunately, and the reason why I love computer science, the material is not something that must be memorized. You simply need to understand it to a point where it can be applied to any type of problem. You are not simply regurgitating information but applying what you have been taught to new problems.

The main issue with the test was simply the worry about remembering the manipulation rules. They are very similar to other properties in math so the rules were not entirely new. A cheat sheet was allowed and with the help of the summarized rules in the course notes, I wrote down all the manipulation rules on one sheet of paper organized under names of the rules.

The benefit of preparing a cheat sheet is not to have the chance to look over or spend time looking over the written material during the test. Instead, at least for me, it serves as a method to remember information. Throughout the course all lecture notes are provided so writing down notes is not necessary along with being difficult while trying to listen. However, when I write something down I tend to never forget it. Everyone has their ways to memorize material, for me that is writing it down.

Lectures throughout the past week have been covering the methods of proving statements and implications. Proofs have always been the weak point and most difficult portion of any math related course. The tutorial handout is posted and contains proof related problems. I will try my best to work through this handout and with the help provided during the tutorial, both my peers and the TA, the material should begin to seem less foreign.

The main problem with proofs is figuring out where to begin. After the first step, proofs usually move along like dominoes.  I am hoping to find tips, tricks, and suggestions when going over solutions during the TA. Examples and observing how others go through proofs is the most beneficial method to learn proofs.