Monday, October 27, 2014

SLOG 6 October 27th 2014

During last week's lectures, we finished covering methods and formats of proofs and moved onto discussing algorithms.  We reviewed some main strategies that we should employ when starting proofs.  For example, to prove universal, we show that there are no counter examples, to prove existential, we just have to find one example.  For implication, we start with the assumption and try to reach the conclusion.  For and statements, we must show that both propositions are true, and we can do this by tackling each proposition independently and then checking to see if both are true.  For or statements, we can also tackle each proposition individually, and as long as one is true, the claim will be true as well.  I learned that these links can also be used to introduce new claims or objects into the proof.  For example, if we know that an implication is true, then we can introduce the consequent when we reach the antecedent in the proof.  Then, we can use the consequent as the antecedent to introduce other implications to eventually reach what we want to show.

We started algorithms by talking about sorting algorithms, which are algorithms used to sort/organize data.  We talked about the the number of steps, or actions that each algorithm takes to complete its task.  When analyzing the speed of algorithms, I can look at their average speed, best case speed, and worst case speed.  For now, I learned that we should focus on looking at algorithms based on their worst speed, because the best speed is not 100% consistent and won't tell us much, and the average speed will take far more effort to calculate.

Lastly, on Friday I worked on a problem involving two drawers and 64 pennies.  To begin, all 64 pennies are in one drawer.  As long as the number of pennies in a drawer is even, I can take half of that number of pennies and move it to the other drawer.  The opening question is to find a way to have 48 pennies in a drawer.  I realized that because I am always splitting the number in half, then the number of pennies in each drawer will always be a combination of some exponent of 2.  For example, 64 is 2^6, which splits into 2^5 and 2^5, which can then split into 2^5+2^4 and 2^4.  2^5+2^4 is 48, so I solved the opening problem without much difficulty.  However the real question was whether or not I can get all numbers from 1 to 64.  When I started thinking about this problem, I realized that since there are two drawers, and the sum of pennies in both is always 64, then if I can get numbers 1 to 32 to show up in one of the drawer, then 32 to 63 will be in the other drawer.  My plan was to create a diagram showing all possible combinations of sums of exponents of 2, and showing that it can represent all 64 numbers, but I was very time and space consuming and I was unable to solve it yet.  I think professor Heap showed this question to us because it is similar to algorithms; though many do the same job, some do it much quicker and require much less space.

No comments:

Post a Comment