Done Assignment 1

Assignment 1 has been handed in, containing material from mathematical and complete induction. I was of course hesitant about this assignment, seeing as my track record with proofs hasn't been great, but spending time with the material well in advance of the due date allowed me to put together the pieces, and hopefully do well on the assignment. Question 1 wasn't that difficult, and after looking over the example involving binary trees in class, I thought of some ideas on how come up with the proof for ternary trees involving height and number of nodes as opposed to whether the number of nodes was odd. Question 2 was relatively pain-free, Question 3 is where I hit my biggest obstacle. I knew my formula for the number of 3-subsets in a set of size n+3 was correct, and I was sure I'd have to incorporate the given formula for the number of 2-subsets in a set of size n+2, but it took a bit of trial and error for me to realize what needed to be done (which was adding the equation for number of 3-subsets in set of size n+3 and equation for number of 2-subsets in set of size n+3 together). Once I figured that out, I had to come up with a reason why those equations added together should equal the number of 3-subsets in a set of size (n+1)+3. This is what took the longest. After staring at my scribbled notes for an embarrassing amount of time and drawing several diagrams, the reason finally came to me (the 2-subsets in the set of size n+3, when added to the new element introduced in the set of size (n+1)+3, would become the new 3-subsets, while the 3-subsets in the original set of size n+3 would still remain in the new set). Does that explanation make sense? I sure hope so, otherwise I won't be doing so well. Anyways, with that off my chest, Question 4 was up next. This one took some thinking. After writing down a few random binary strings that began and ended with the same bit, it seemed true that they did contain an even number of occurrences of subsets from {01, 10}. Upon further inspection of the strings I wrote down, I discovered why. How to make a proof that made sense was another story. I remembered the stamp example from class and saw how this proof might have some similarities to that one. The string added to a smaller string to get to the current string had to follow a formula, otherwise there would be another, bigger string that could be used to get to the current string. Using this formula, proving that either 0 or 2 new occurrences of subsets from {01, 10) were added to an already even number of occurrences, resulting in an even number of occurrences, came naturally.

Overall, I think I did a pretty good job with Assignment 1, and it definitely helped reinforce the material involved.

How I've Missed Proofs!

First time doing any kind of blog, hoping I don't make a complete mess of things. CSC236 has started, which is of course the continuation of my favourite course from first year, CSC165, in which I achieved a whopping 53%. I do intend to do better this year, I already feel like I'm grasping the content much more than I was in 165, despite my recent failure in the quiz. Speaking of the quiz, I completed both quiz practice questions, and went over them before the tutorial. From the tutorial I knew that I did them correctly, but I feel as if the time spent going over the questions sort of messed me up. It seemed as though it was meant to help the people who didn't do the questions, and the structure of the proofs in the tutorial was slightly different than the one shown in class. Of course, if I really knew my stuff I wouldn't be making excuses for messing up on such a simple one question quiz.

Did I forget almost everything about proofs over the summer? Probably. Simple Induction and Complete Induction seem almost foreign to me, but I will try my best, with hopefully better results than last year.

I suppose I should discuss my feelings on the methods of induction we've been taught so far in this course. Simple Induction seems straightforward enough (obviously not enough to pass a one-question quiz though) and Complete Induction makes sense to me. Everything seems to make sense when it's explained for you step-by-step doesn't it? It's when you have to figure it out that you realize you have no idea what you're doing for the first five to ten minutes. That's how you, or at least I, learn I guess. In retrospect, I probably should have done more than the two practice questions, I'll make a point of spending more time with this course's material, as I know from experience that proofs are not my strong suit, and neither is discussing them, as I'm sure you'll find out if you continue to read what is sure to be the greatest proofs blog ever created by a student from Victoria University (hopefully you get that one). Happy reading!