Polya Problem Solving

So if I remembered correctly I have to tackle a problem with Polya's problem solving strategy. The problem have chosen is really simple, yet the goal is that I carry out Polya's problem solving strategy, and an easy problem does not stop me from doing that. So the question is: Is every sequence of natural numbers finite and explain?

1. Understand the problem
So to answer the question, I either say yes and prove it, or say no and find an example of an infinite sequence of natural numbers.

2. Make a plan
This is one of those questions that are so obvious that direct reasoning can solve it. So the plan is to use direct reasoning.

3. Carry out the plan
It is less work to try to say no first because providing a counterexample is less work than proving something. So I will start by saying no and I will try to find a counterexample. So I know that there are an infinite number of natural numbers since if n is a natural number then n+1 is also. So the sequence 1, 2, 3, 4... is an infinite sequence of natural numbers for each term n, the next term is n+1.

4. Reflect
Saying no worked pretty well because if I had said yes I would have to deal with a non-working proof then conclude that the answer is no which takes a long time. So in a problem where I have no idea whether the answer is yes or no, I should first try the answer that has less work.

DFSA

DFSA was very scary when it came up because the name was very long and things with long names tend to be complicated. Luckily it seems pretty simple, at least the DFSAs relevant to CSC236. I am unsure on what it means to prove every single case at the same time but I assume it will be proven next class. So I really have nothing to say until the proof is presented.

As well, the equivalent RE properties resemble mathematical ones which makes them very easy to remember, although I hope memorization the name of each property is not required. Is it required?

Language?

When class first started I thought "this should be pretty easy, just some symbols and stick them together" but it started going downhill after the Kleene star since I was confused how the * is applied to the language when previously it applied to sigma, which is a set of symbols and how the * applied to the language gives the same result as * applied to the set of symbols in the language.

So I was confused for awhile until the examples came which I surprisingly got them somewhat correct since I did not understand the notations at all. Where did the (1 + 0)* come from when the Kleene star was either applied to the set of characters or the set of all strings in L? (1 + 0) does not use { } so how is it a set? So I kind of guessed that 1 + 0 = {1, 0} because of the + symbol meant union for languages although it was never explicitly said that it applied to symbols as well. All that was said was that (R + S) wasn't really defined, like how saying 1 + 3 is a valid arithmatic expression even if I did not know what 1 + 3 means. To me it would make somewhat more sense if it was ({1} + {0})* instead since (1 + 0)* could be taken as ("10")* for a new learner.

The difference between a regular expression and language is confusing as well so I hope I can differentiate them as I am type this. So according to my understanding, a language is the set of all strings formed by a regular expression. For example, L((10)*) would be the set of all strings {empty string, 10, 1010, ...}. A regular expression on the other hand is not the set of strings but identifies the set of strings. Ok, so maybe that is why (1 + 0)* is used instead because ({1}, {0})* would be a language instead of a regular expression?

Then there's the proof that was never completed in class but whose outline was given. I would prefer the proof (perhaps next class?) since I want to know the proper terminologies to use in this type of proofs.

Iterative Correctness

Wow, iterative correctness is so much more difficult then its recursive counter part. Iteration is generally easier to see than recursion but theirs proofs is the other way around, partly because induction is so close to recursion; they are like siblings. Iteration is too different. First there is just a bunch of variables in iteration and keeping track of them is a task in itself. Then there is the scary loop invariant. It is one of those things that a person just "sees" and unfortunately I am not one of those people who is able to just "see" it. In other words, I am screwed. As well there's a lot more parts to proving iteration compared to recursion. Argh! I am just going to memorize every type of iterative proof in class and then apply the corresponding loop invariant on tests and exams! It is likely not the best method but it should work, hopefully.

Program Correctness

So to me program correctness is just another thing that can be proved with induction. I don't know even what to talk about this post - it's pretty much the same. At least it's more about the computer aspect now, since the proofs before had nothing to do with computing.

Oh and I found out on Friday that assignment 2 is due Monday! Midterms must have diverted my attention from it. I hope the submission will be problem free this time.

Divide and Conquer

Wow, that was a long proof for T(n) for merge sort! I understood each step of it but there's no way I could re-prove everything on my own. I would never think of the monotonicity portion of the proof on my own. Well, I would, but it would definitely take a while and not within the time limits of a test. Luckily Prof. Heap says he does not like to post test questions where students are required to regurgitate proofs so yay!

I find CSC236 to be much more interesting than other courses. Perhaps it is the way it is presented or the frequent "10 minutes to try out the example" interactivity that makes the 3 hour night course far less boring than other 3 hour courses. The surplus of room allowing for a comfortable seating space does not hurt either.

Half an Induction

First off, the test. I found it to be a good test because it was fair. There was no insanely difficult question that math tests are infamous for. All of the questions can be readily answered if lecture material was properly digested. The first question (sets omitting 1, 2 or both} is easily proved with the same method as the "number of subsets = 2^n" example in class. The proof to the second question is obvious when using the standard proof for a > b. The third question was reminiscent of CSC236 questions which isn't so bad.

As for the lecture, finding closed formulas was pretty neat because I found the method for it ingenious for some reason. One thing I'm unsure of is why the family of solutions is formed by a linear combination of the roots. I've learned to accept it something like a fact of life or "because Prof. Heap said so" but I would like to know the reason. The overall algorithm is pretty straightforward though so it makes easy test questions, hopefully.

The induction for sets is very close to the P(n) => P(n+1) type of induction. I find it interesting how something can be so similar yet different at the same time. I find it slightly more difficult than the P(n) => P(n+1) type though since I prefer numbers instead of word explanations, and it seems to be necessary to incorporate at least some of it for find induction for recursively defined sets.

The last thing is my assignment 1 apparently did not submit correctly resulting in a completely unreadable format. At the time of this posting, I have a 0% for it. I think this is very unfortunate since I believe that a mark should reflect understanding of course material and effort given instead of unknown technological errors during submission, especially because I believe the error is not caused by me and/or I have no way to know of this error before it occurs. I think the CDF submission site should have the feature to view the contents of submitted files instead of just listing the files and file sizes which would prevent incidents like this from occurring.. I hope Prof. Heap is able to recover the file and remark it or redistribute the weight of this assignment to other course work.

Recu[recu[recu[recu...

The recursion lectures were pretty straightforward for the most part since I think everyone in CSC236 would have some sort of programming experience with recursion meaning the concept is very simple. Proving recursion is very natural with induction and since CSC165 and the beginning of CSC236 spent plenty of time dealing with that, that wasn't very difficult either.

However some parts were quite confusing. The first part was the number of binary strings without pairs of 0's. ?It was fine until the "the only way to add a 0 without changing anything is the 10" part. So ending in "x1" and "10" was taken care of, what about "00"? Don't we need to count that? Now that I think about it it's pretty obvious that strings ending in "00" have a pair of 0's in them but for some reason I kept thinking the question was binary strings with pairs of 0's instead of without so I was confused for awhile until I kept scribbling at my own piece of paper to figure it out. I felt that Prof. Heap could have spent some more time on explaining that part since it was the crux of the algorithm. I should have just asked but there exists the fear of the stigma of appearing foolish.

The second part was the complexity of binary search example. Part of the confusion came from the fact that I forgot all about big-O and its friends over the summer. I recall Prof. Heap giving a brief review but it was much too brief. Luckily big-O crawled out from the corners of my brain rather quickly. But then came the part with the proof. The massive amount of marks on the slide in conjunction to the calculations errors just left me dazed. Of course I did not know they were errors and assumed that I was missing something so I was frantically trying to find out what I had missed. The whole structure of the presentation of that part was very messy and confusing because of the erasing of parts. Eventually Prof. Heap realized the errors and everything went back to fine and dandy but the whole ordeal just burnt my tiny brain to a crisp. Eventually after staring at it for a bit though, I got it.

Principle of Well Orderingthingymajig

What? I think the example on the Principle of Well Ordering was definitely rushed since it was covered in less than an hour of class time and seeing as how it is "half" an induction method, I wished more time was spent on it. Does R = {...} have a smallest element? Yes obviously, and then after a long and to me confusing discussion about some variables R, n, q, m, r and etc., then next slide comes up and something is proved quickly with references to the previous page, which I could not easily refer to since it's not on screen and I have not written everything down because I was confused enough to not know what to write down.

Luckily I just read the slides over and through some pondering figured out what Prof. Heap was saying and now it all makes sense. Yay! The other stuff was kind of self-explanatory with the chocolate and trees.