Post Five

Big O, Omega, Theta, Halt and reduction

    These were by far my favorite topics in the course. Big O, Omega and theta especially because it managed to tie in everything from the course up until that point and tie it into computer science. Not that the prior knowledge wasn't useful or important in its own right but it was great being able to tie it all so neatly into something more distinctly computer science related.

    The interesting thing about the proof for why a function Halt does not exist was, at least for me, counter intuitive at first glance. Though as I began to understand it better it started to make more sense. Reduction was also somewhat confusing at first because the function that you are trying to show cannot exist is irrelevant. Eventually though it clicked for me that the important thing is what we know about Halt and not the function we are, in a given situation, trying to show is not computable.  That is, if we can implement Halt by assuming the given function is computable then by contradiction it cannot be computable (since we know Halt is not computable).

Post Four

Term Test Two

    I thought this test was well written and even easier than the first. That being said I still managed to get, what I consider the easiest of the three questions given, wrong. My main mistake was fairly simple, I completely disregarded the negation of the statement mid proof and made an assumption for q rather than very simply showing its existence, q being the first q in the statement. My reasoning behind it at the time was that the value of this q in and of itself was irrelevant in the overall proof. That is, I did not need to directly use it when showing there are no q2, q2 being the other q in the statement, such that m= … But, as should be obvious to most readers, my opinion of the values relevancy is in itself irrelevant. Because I was, in the negation of the original statement, claiming that there existed a q I was thereby obligated to clearly show its existence regardless of its usefulness or obviousness. On the bright side though, I can certainly say that I'll never make the same mistake again.

    Another interesting thing about my test is the answer I gave for the third question. Mine was different than sample solution provided. That is because I decided to, out of comfort with the method itself, prove the statement by contradiction rather than directly. Looking back, the direct proof is only, at least in my case, marginally easier. To prove the given statement by contradiction I simply showed that if floor(x) + 7 <= x + 6 then there exists a z, in this case floor(x) + 1, that proves the negation of the definition of floor which is a contradiction. The reason I say that the solution provided gives only a marginally easier proof is because I encountered a statement similar to this one where contradiction was used in the proof prior to the test so I already knew exactly what to do to prove it by using contradiction.

Post Three

Products of Sums

1) Understanding the problem

What is the problem at hand? Given n, a positive integer, find the list, whose sum is n, with the largest product.

Some sample data:

n	Lists	P
1	[1]	1
2	[1,1], [2]	2
3	[1,1,1], [1,2], [3]	3
4	[1,1,1,1], [1,1,2], [2,2], [3,1], [4]	4
5	[1,1,1,1,1], [2,2,1], [3,2]...	6
6	[1,1,1,1,1,1], [2,2,2], [4,2], [3,2,1], [3,3]...	9
7	[1,1,1,1,1,1,1], [2,2,2,1], [4,2,1], [3,3,1], [3,2,2], [3,4]...	12
8	[1,1,1,1,1,1,1,1], [2,2,2,2], [4,4], [3,3,2]...	16
9	[1,1,1,1,1,1,1,1,1], [2,2,2,2,1], [4,4,1], [3,2,2,2], [3,4,2], [3,3,3]...	27

(I found some more lists for higher n values but this is enough to see what's happening)

One thing that we need to strive for here is to process this data into a general form in order to satisfy the problem at hand easily given any integer n.

2) Devising a plan

So, where do we go from here? Well we have all this data, we might as well put it to use. From what I could gather the commonality between the lists with the largest product is that they are all made up of, exclusively, the numbers 2, 3 and 4. But since 2+2=4 and 2*2=4 we can reduce the 4's and say the lists are all made up of 2 and 3. We also note that 3's seem to be the optimal choice as long as choosing a 3 does not mean a 1 will be in the list.

Our plan then is to generalize and see just how much 3's we can get out of some number n without having a remainder of 1.

3) Carry out the plan

We can look at the remainder of dividing some number by 3 and approach this on a case by case basis.

1. n % 3 = 0
2. n % 3 = 1
3. n % 3 = 2

1. The list is made up of n/3 threes.
2. The list is made up of (n-4)/3 threes and 1 four (or 2 twos)
   This is because when n % 3 = 1 then (n-4) % 3 = 0. We add 4 to the list to compensate for subtracting. This method allows us to get the most 3's out of n without having a 1 in the final list.
3. The list is made up of floor(n/3) threes along with the remainder, 1 two.

So given some integer n we can easily find the list we want by following these three cases.