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.