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.
Sunday, October 26, 2008
Saturday, October 18, 2008
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.
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.
Saturday, October 11, 2008
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.
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.
Saturday, October 4, 2008
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.
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.
Subscribe to:
Posts (Atom)