Problem Solving Blog/11th (final) blog :3

So I've finally decided on the problem that I'm going to try to solve.
I choose you, penny piles!
I liked this problem because it reminded me of binary code. Since there are only two actions that can be done the procedure can be modeled by a Tree structure :)

There are some general trends I've noticed.

1. It is symmetrical, as in the numbers are paired up, so if you have x, y you get two possible combinations out all the range [0, 64] since x + y = 64. Since y, x and x, y yield you the same two combinations you only really need to make one of these equal to all numbers from [0, 64].

2. From this point above, I conclude that if you can find all the combination for [0, 32], then you
can prove the same thing for every even numbers in range of [0, 64].

Let's say you play around 64 pennies and breaks it in 32, 32
Half of that is 16, 16.
This can be obtained simply by splitting 0, 32.

Let's look at another example.
Let's say you get 32, 32 -> 16, 48 - > 40, 24
Half of that would be 20, 12
An equivalent of that in 32 penny pile would be 16, 16 -> 24, 8 -> 12, 20


3. But since you can get odd numbers from dividing even numbers in half, this takes care of the lower half of the odd numbers.

Here's an example. If you find the value of 22, 42 in the 64-pile hen you can conclude that
11, 21 is in the 32-pile.
 But if the 32-pile has all the numbers from [0, 32] then 22, 42 will definitely be a valid combination for 64-pile because of rule 2.

I'm going to list combinations by brute force, but knowing the patterns from above, I can just do the 32-pile by brute force, and that will prove that any x, y combination is valid for the 64 pile for all x and y that is an even number.

0, 32
16, 16
8, 24
4, 28
2, 30
1, 31
------
You can do it backwards, in this case I want 3
(Any '->' is meant to be an alternative path, that might help find other numbers)
3, 29
6, 26 -> 19, 13
12, 20 -> 22, 10 -> 27, 5 or  11, 21
24, 8 -> This is in the first list of numbers, so this is valid.
------
Want 7
7, 25
14, 18 -> 23, 9
28, 4 -> This is in the first list of numbers, so this is valid.
------
want 15
15, 17
30, 2 -> This is in the first list of numbers, so this is valid.

I proved all the numbers from [0, 16], but if you look at their partner, they are numbers from[16, 32]

This proves all the numbers from [0, 32] and all the even numbers from [32, 64] for 64-pile
So we're missing
33, 31
35, 29
37, 27
39, 25
41, 23....
Notice how their partners are numbers from [0, 32]?
That's right, they're just in the form of y, x instead of x, y
Therefore it is possible to get any number from range[0, 64] in the 64-pile case.

One more Week!/10th week

Just one more week of class left, then it'll be exam period. I think it was worthy to mention that I actually remembered everything I learned in calculus, and since we did proving involving L'Hopital's rule at the end of the week last week, all the materials just rushed in my head. But I fully get the concept of rationalizing two function to see if one is increasing at a faster rate than the other.

We went into halt problems this week. So far I understand the concept of halt and I think the hardest part of understanding halt is perhaps the acceptance of knowing that it does not work. Assignment 3 does not seem to complicated and I hope that the exam isn't too hard.

Test 2 Results/9th Week

I was not pleased with my test mark. But I have to admit, I really did screw up on the first question. I completely misread the question and now looking back at it I realized how stupid the mistake was. It was a really straightforward question, we've done it in class, in tutorials, and even some of the questions on A2 had similar concepts. At least the test mark wouldn't affect my overall mark by too much. Just have to study really hard and keep a clear head for the exam.

Also feeling a bit sad since there are only two weeks left of school. However, that also means that exam seasons are coming up, I should start getting ready to study away for my exams. There are only a couple more evaluation that are to be made before the final exam, there's the quizzes, A3, and this slog.

Also at the end of last class Prof.Heap mentioned that we're starting with halting functions soon, if I remembered correctly he mentioned this topic at the beginning of the course stating that the hardest part of this course is probably at the beginning, and near the end when we do halting functions, this had made me anxious about this particular topic.

P.S. In 148 we learned the 'Heap' ADT and that reminded we of Prof. Heap.

Second Test/8th week

So in the lectures we talked about more proofs involving upper bound and lower bound, then we started doing proofs involving polynomials. It all seemed pretty trivial and all we had to do was come up with numbers that will always to strictly greater (>) or strictly less than (<) and maintain that inequality.

I couldn't prep really well for the test, but on the contrary I think I did well. I did make a cheat sheet but it is just general guide lines to follow to prove things. I also wrote down some types of proofs and how one would approach them. However, I was confident in my understanding with proofs since I knew how to do question 1 - 5 for assignment 2 before the solution was posted. The first two questions were really straight forward since we've done many similar problems either inside or outside of class. The last question took a bit of thought but I did manage to do it with the definition that was given.

Things are looking good, I hope it stays this way.

Complexity/7th week

This blog was posted later than I expected as I was kept busy by other work. I have a bad feeling about the next couple of weeks, especially leading up to exam seasons.

One thing that I have to mention is this confusion involving counting the steps. During the tutorial, every single operation was counted as a step, so it is possible to count multiple steps for a single line. I'm pretty sure that someone brought this up in class. Eventually I realized that it doesn't matter how you count the steps, it just differs by a constant factor so it does not change the bigger picture.

Maximum slice looked really long, and tough. I couldn't really follow it readily in class. But after re-reading the slides and notes a couple of times I am starting to understand it better. It just gets really hectic since you have i which depend on n, and then j depends on i, and the number of time the second while loop executes depends on i and n, specifically from i + 1 up to n. I also had a friend who showed the notes from the last term and that helped clear some things up.

I hope everyone has a great weekend and preferably start studying for next weeks test, it did not seem too harsh since Prof. Heap mentioned that things involving complexity(steps, upper&lower bounds) won't be on the test.

Proofs & Complexity / 6th week

I'm uncertain on whether or not if we should've written a blog during the reading week, but I forgot anyways, and technically we didn't really 'learn' anything during the reading week, so I'm just going to let that one go.

Sorry about the lateness of this blog, my blogs are usually written on Wednesday but I was kept busy with my midterms and I kind of forgot, I promise that my next blog will be written on the Wednesday.

All non-course related materials aside, we started doing proofs that can get a bit more complicated and now we are not specifically told whether or not if the statement is valid. This requires us to do a little bit of extra work at the beginning figuring out whether or not if we want to prove, or to disprove the statement given. This is probably done by substituting in a bunch of examples, if the majority of them works then look for counter-examples that do not work.

Another thing we started this week is complexity, we actually did this on friday so if I'd written this blog on Wednesday it would not have been a part of this blog. I remember doing Complexity in CSC108 and talking about it brought back memories of that class. However, in 108 we simply talked about the program run time and how a program normally runs n times, but if you have a nested for loop the running time becomes n ** 2. We took it a 'step' further in class and talked about steps. So far it seems like the complexity stuff is not too hard, all you have to do is break everything down into subgroups and add them all together to find out the total step of the run time.

More proofs/5th week

So far we've been doing proofs for 2 weeks straight, I can't really complain much, it's mostly structural. However, it does seem like the proofs are getting longer and longer. On a side note, for the tutorial this week, I thought we were going to write an actual proof, but it turns out we just had to write down the structure for the proof. I mean, the actual proof is not that much off compared to the structure, there were just a couple of blanks that needs to be filled.

So we had our assignment 1 mark back, and I was not happy with my mark. I mean I actually understood the question, but looking back now I just realized I probably didn't phrase certain things the way I should of. But since the marks are set I should probably just worry about getting a good mark for assignment 2. It kind of sucked since I also realized that I messed up on my last question on the test. But I did do the contra-positive, converse, and negation right, I just started off with the wrong implication, I hope I get part marks for that.