Week 8

Summary

With proofs finished, the new material shifted focus to algorithms and efficiency.  The algorithms discussed were sorting algorithms and the upper/lower-bounds of of these implementations were analyzed.

Challenges/Thoughts

While other courses have also taught efficiency of sorting algorithms to some degree, the upper-bound and lower-bound was a new concept for me. The difficult part was working with a code to find the number of iterations in its best and worst case scenarios. While the upper-bound and lower-bound allows over and under-estimations of iterations for the appropriate situation, I still found it difficult to accumulate all the steps and write it in manipulable math symbols. Hopefully, this will become easier with more practice.

Example

During lecture, the penny piles problem was mentioned. The professor asked if there was any number that could not be made between 0 and 64 by transferring half of one box's contents at a time (given that the contents contain and even number of coins) where one box started with 0 and the other at 64.

The professor gave some hints to approach the problem. The ones that I found helpful were to work backwards and to find relationships of smaller cases. In the case of smaller cases, he told us that you could scale the problem down. It 12 can be achieved when starting with 0 and 32, 24 can be achieved with 0 and 64 because the relationship is scaled by factor of 2.

With this in mind, I tried finding a relationship between reaching a smaller number and a larger number from the same number of coins. I found that, any even number in the range is solvable and that they all eventually reached 16 on one side and 48 on the other before reaching the solution. Since this was true, all even numbers in the range must work as well because with the allowed operations and total number of coins, if one side is odd, so must the other side. To get to an odd number, the step prior to reaching that odd number would have been contained double the coins of one side while the other would have contained what it has now minus what the first side contained (odd - odd). Since both boxes would have required an even number of coins prior to reaching that even number, and since all even numbers are reachable, all even numbers within the range 0 to 64 must also be solvable.

Weeks 6 and 7

Summary

The focus over these couple weeks were the structure of proofs and strategies for proving statements. While week 6 focused more on the structure and general thought process of how to approach proofs, week 7 covered the full proof including the numbers or variables required to satisfy or falsify a statement.

Challenges/Thoughts

The real challenge of proofs came from the intuition and thinking required to first understand a statement. While the proof structure has a general template to follow for all statements, each statement is different and requires what is being said to be understood in English. I also learned that while a statement may seem trivial, it is actually not so simple to write down why it is true in formal proof structure.

Example

The example covered in lecture that floor of x (the largest integer that is less than or equal to x) is always smaller than x + 1 was quite interesting. When you read this in English, it seems so obvious that something smaller than or equal to x must be smaller than x + 1, but to convert that into a formal proof requires practice.

In mathematical symbols (LaTeX):
$\forall  x \in R, [x] < x + 1$

First we assume a general x' that is a real number $R$.Assume $x in R$

A proof requires all the thoughts required to solve a problem, even thoughts that seem trivial. So we must first state that:
    Then [x] <= x  # Here we must justify why; and in this case it is due to the definition of floor.

Then we can write the following:
    Then x < x + 1  # This is a tautology, always true.

Putting that together:
    Then [x] <= x < x + 1
    Then [x] < x + 1  # Transitivity

Since, the general number x satisfies [x] < x + 1, the statement is true.