Week 11

Problem Solving: Penny Piles
Using operations
        1. 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 1 is disallowed.
        2. 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 2 is disallowed.
Which numbers in the range [0,64], cannot be reached when starting from 64 pennies in the left drawer and 0 on the right?

Step 1: Understand the Problem
To understand this problem, as computer scientists it's only natural to analyze the input and outputs. In this case, the input would be a number the numbers in the range [0,64]. The output would either be true or false for each particular input. Now, our output is either true or false depending on whether or not we can find this path from our starting point [Left: 64, Right: 0] to [Left: n, Right: 64 - n] or [Left: 64 - n, Right: n].
Step 2: Devise a plan
To devise a plan, we must break down the problem into simpler steps. We must analyze whether any parts of the problem are related. For example, if we take on step further from [Left: 64, Right: 0], we would see the only possible move is to move half the pennies from the left to the right. Now we have
[Left: 32, Right: 32]. Since that was the only possibility, we can now effectively assume starting at [Left: 64, Right: 0] and [Left: 32, Right: 32] will result in the same output. Furthermore, since [Left: 32, Right: 32] is identical, we may also assume if we can reach [Left: n, Right: 64 - n] if and only if we can reach [Left: 64 - n, Right: n]. Therefore we can limit the problem to one side, return True if there is a path from  [Left: 32, Right: 32] to [Left: n, Right: 64 - n] using operations 1 and 2.

Now that the problem has been simplified, we can analyze the structure of the problem. There are now 2 possible moves from the position [Left: 32, Right: 32]. And for each of those moves there will be 2 more possibilities etc (Binary Tree). To illustrate a visual diagram of the problem, a tree would work perfectly where each branch would represent a possible path and each leaf would be a solution. If the given input is not in the tree, then there is no path connecting it to the root, and therefore that input is unreachable.
Therefore, to solve this problem, we may draw a tree of all possible paths and results to figure out which numbers are possible and which are not.
Step 3: Carry out the plan
Create the tree:

Note that inverses are effectively the same solution. Ex. 52:12 can be reached iff 12:52 can be reached. (In this particular tree because 32:32 has both drawers with equal amounts of pennies)

Step 4: Looking Back:
This solution results in finding all possible results of starting from a certain point. If a number is not in the tree, then it is not possible to reach it.
This solution can be extended to numerous identical problems. For example, if given a different starting point, we could generalize a new tree for that particular convention.

Week 10

This week, new and different concepts were introduced throughout lectures. I never really thought about the limits of computer science seeing as it's regarded as still a new and expanding field. So when Danny introduced functions that could not be programmed, I was quite intrigued. I understand that the halt function cannot work on all functions (in the case of the function calling halt within itself, EX navel gaze), and many other functions that would extend to halt, also cannot be implemented because halt cannot be implemented.
Another new concept introduced this week was the concept of different sized infinite sets. I find the concept of infinite sets and the definition of countable to be a tricky and un-natural concept. For finite sets, the definition of one-to-one and onto make sense, however, I find it hard to visualize this concept with infinite sets. For example, the definition of one-to-one and onto is satisfied with the sets of natural numbers, even natural numbers, and odd natural numbers(compared to natural numbers). Therefore, the  set of natural numbers has the same size as the set of even natural numbers AND the same size as the odd natural numbers, although the set of natural numbers contains BOTH the even and odd natural numbers.

week 9

This week we learned about proving more complicated big O and big Omega questions. Although they appear to be complicated at first, it seems the trend is if you follow the proof structure taught throughout the course, and simply write your given definitions (in the antecedent), choosing your c and b don't seem to be all to difficult.

My only concern is that for most of the questions, we were given whether the statement was true or false, and surprisingly some of the statements I believed to be true, were false.

Week 8

The main event this week was the second term test, and I had learned that solving proofs under time pressure could be very difficult and stressful. I found it very challenging to really understand what I was proving and to think of an example ( existential proof) of an instance that satisfied the proof. I was mainly stuck on the 2nd question for the majority of the test. I had written the proof structure for the 2nd and 3rd questions to ensure I would get at least part marks for them. It was not until after the term test I had realized that the 3rd proof on the test was extremely similar to the proof done in assignment 2. With a clear mind, I believe I would have been able realize this, but because of the time constraint and lack of review, sadly I was not.

I have learned that I should review much more than I did in preparation for this test.

Week 7~

At the end of the last week, we were given an in class exercise where we were expected to devise a plan or algorithm to solve a certain problem. After help from Danny, as a programmer, it was quite simple to understand the first solution or plan; work backwards. This meant, start from the solution, and keep working back until you reach the starting point. If you cannot reach the start, then the solution is not possible. Now, the second solution is what stood out to me. Interestingly, we could model this problem as a tree (currently exploring this topic in CSC 148) and view all the possible cases or results. I always find it astonishing when courses relate together, even in simple cases such as this.

During the week, I worked on assignment 2 and have no experienced how simple it is to prove something that is false, or disproof something true. I was convinced claim 1.2 was true, until told otherwise at Danny's office hours. It was one of those moments of disbelief, followed by the feeling of utter stupidity. It seemed I missed a case in my proof, causing it to collapse. It's interesting how fragile a "for all" statement is, and how there are cases that are hard to consider until told to you. As a computer scientist, I need to improve this and learn how to explore and consider all possible cases.

Week 6

This week we continued to emphasize upon our understanding of proof structures. We've now covered direct proof of implications (assume antecedent,prove consequent), indirect proof of implication (assume not consequent, prove antecedent), and general ideas such as ;assume X is in R, then conclude for all R.

Furthermore, professor Heap went over how to prove/disprove statements. He also stated that the only way to understand whether a statement is true or false is to prove/disprove it. Many questions in assignment 2 involve proving/disproving statements without knowing whether they are true or false. Therefore, the only way to approach these is to go by gut feeling (I assume) and try to prove or disprove, and if that doesn't work out, prove the negation.

Week 5

Term test 1 marks were handed out this week, and to my surprise, I had received perfect. In my last blog I posted, and stated that I did not double check any of my answers and any mistakes were due to poor test-taking habits. Fortunately, these habits did not cost me marks on this particular test.

The material covered on term test 1 was tricky, perhaps not difficult, but I felt that it was quite easy to make mistakes. Unfortunately, i found the material taught this week to be rather confusing and difficult. (I do not have a strong background in math) Just the proof structures seem simple enough, with indentations, and concluding each different level of indent. This makes sense to me since I enjoy programming, but the difficult part is the center of the proof, and how to actually prove the statement. (usually with math)

I look forward to the tutorial exercises since I know in order to solve these, I will be forced to learn and develop at least some sense of how to approach proofs.