Program correctness sounds fun, given a precondition and post condition, you try to hack your way to break the program, what makes a program correct? or it works?, personally, i think when some one says "yay it worked" means given a correct input, it spits out the correct output, but i personally don't believe programs to "work" 100% correctly, but hey only precondition and post conditions needs to be satisfied ;)
even if i code a program, i don't think it'll work 100% correct, i'm sure someone will be able to hack or break apart my program, but hey, if it satisfies what the assignment was required, why do extra work? (and i'm lazy to find all cases, but i do have to do that for 207 otherwise i won't be having a good mark for test cases! ;( ) (speaking of hacking, that reminds me of the movie "Live Free or Die Hard" hehe where hackers were able to hack into FBI network(talk about something important as that..) or the national database.. (i sure hope it doesn't happen here! or there goes all my money)
the last couple of lectures certainly improved my understanding of induction, not just the simple "you have T(n) and prove T(n+1) thing", but allowed me to understand that we make a claim, assume something, then using that hypothesis, prove what we want to prove, which is not limited to just the "n+1" case, such as proving T(n) >= logn or G(n) <= F(n) as the question in the assignment.
o well now that i have the assignment and problem set out of the way, onward to study for midterms and finish other assignments :(
Sunday, October 26, 2008
Wednesday, October 22, 2008
Problem set 4 and Assignment 2
with most of the midterms and assingment out of the way, i finally had a time to sit down and look at the problem set 4 and assignment 2 which is due next monday
looking at problem set 4, i think i can breeze through it with ease since it was a prove by induction that precondition => postcondition (if its true), which is almost the same thing as what we did today in class
looking at assignment 2, it feels pretty alright, #2 is about finding close form and proving it, i already found some kind of pattern for it, now i have to just put it down on paper and prove it.
#3 shouldn't be too bad either, although i do have to find a algorithm to generate the "steps" and then just have to prove that G(n) is less or equal to the fibonacci numbers
#4 is about the same as the problem set 4, proving precondition implies postcondition, the only thing i have to refresh on for #4 is the thing about run-time and a bound for it, but i think we have already done something similar in class with the time complexity of mergesort which is nlogn (i think it was mergesort)
only thing i have a problem is question 1, i forgot what ternary trees are, so i will have to refresh my memory on that.
overall i hope i can finish this by the weekend so i can work on my other assignments and study for 2 of my midterms :)
looking at problem set 4, i think i can breeze through it with ease since it was a prove by induction that precondition => postcondition (if its true), which is almost the same thing as what we did today in class
looking at assignment 2, it feels pretty alright, #2 is about finding close form and proving it, i already found some kind of pattern for it, now i have to just put it down on paper and prove it.
#3 shouldn't be too bad either, although i do have to find a algorithm to generate the "steps" and then just have to prove that G(n) is less or equal to the fibonacci numbers
#4 is about the same as the problem set 4, proving precondition implies postcondition, the only thing i have to refresh on for #4 is the thing about run-time and a bound for it, but i think we have already done something similar in class with the time complexity of mergesort which is nlogn (i think it was mergesort)
only thing i have a problem is question 1, i forgot what ternary trees are, so i will have to refresh my memory on that.
overall i hope i can finish this by the weekend so i can work on my other assignments and study for 2 of my midterms :)
Wednesday, October 15, 2008
Problem Set 3
So after reading problem set 3, and writing a lot of draft work and equating equations together, i finally came up with the closed-form for G(n), although certainly not something like we've done in class, but it certainly only requires a value n, and nothing else to solve for G(n) and satisfy closed-form expressions, and it works, now that is left for me to do, is write out the proof.
Monday, October 13, 2008
Term Test #1
i find Term Test #1 to be fair, i knew the answers to all the questions unfortunately, in the 50 mins period span, i managed to only write a structure and a few of the cases for #3 (which was the subset question) without finish proofing it.
Question 1 was pretty straight forward, using simple induction and proof 3^n > n^3 + 10, basically it was algebra and inequality manipulation, going from 3^(n+1) to showing its greater than (n+1)^3 + 10.
In Question 2, although some people i talked to used complete induction, i just used simple, it was like the sum of the fib numbers, we just need to proof that f(n) > 2n, with this, i first say f(n+1) = f(n-1) + f(n), then by using the def of f(n) i rearranged so that f(n-1) = f(n) - f(n-2), such that its 2f(n) - f(n-2), and then everything works itself from there using the I.H. With a bit manipulation we arrive to 2(n+1) which is what we wanted.
In question 3, it was number of subsets such that its 3*2^n-2 if 1 or 2 or both are omitted. It was a fairly simple proof using cases, split it into 1 being omitted, 2 being omitted, then both elements being omitted, and soon enough adding them up, and taking away elements that were repeated(such as empty case), we would be able to arrive at our conclusion. Unfortunately i spent some time thinking about the inequalities manipulation in question 1, and thus not had time to finish question3, however i did put a conclusion in even though i did not finish the proof, as i see the marking scheme from the past term test that marks were taken off if certain things were omitted. funny how i mention omitted things and question 3 has the omit elements.
maybe i can proof using induction my test mark if the n required things were omitted eh?
Question 1 was pretty straight forward, using simple induction and proof 3^n > n^3 + 10, basically it was algebra and inequality manipulation, going from 3^(n+1) to showing its greater than (n+1)^3 + 10.
In Question 2, although some people i talked to used complete induction, i just used simple, it was like the sum of the fib numbers, we just need to proof that f(n) > 2n, with this, i first say f(n+1) = f(n-1) + f(n), then by using the def of f(n) i rearranged so that f(n-1) = f(n) - f(n-2), such that its 2f(n) - f(n-2), and then everything works itself from there using the I.H. With a bit manipulation we arrive to 2(n+1) which is what we wanted.
In question 3, it was number of subsets such that its 3*2^n-2 if 1 or 2 or both are omitted. It was a fairly simple proof using cases, split it into 1 being omitted, 2 being omitted, then both elements being omitted, and soon enough adding them up, and taking away elements that were repeated(such as empty case), we would be able to arrive at our conclusion. Unfortunately i spent some time thinking about the inequalities manipulation in question 1, and thus not had time to finish question3, however i did put a conclusion in even though i did not finish the proof, as i see the marking scheme from the past term test that marks were taken off if certain things were omitted. funny how i mention omitted things and question 3 has the omit elements.
maybe i can proof using induction my test mark if the n required things were omitted eh?
Sunday, October 5, 2008
Recursion
One of the things i love the most, short and simple. Looking at the lectures done the past week about recursive functions and how to prove them by induction seems the same, most of the time you might need more than one base case(fibonacci numbers), some times you only need one! like the function we did in class(the sum of the fibonacci numbers).
looking past that, we also try to do recursive functions in code, i personally don't know python, and am more familiar with java and the other programming languages, but using recursion in code is pretty neat, although, not every requires recursion as it does take up quite a heap of memory space, going forward once then backwards to output the answer. Recursion quite easy and simple, define a basecase, then for the rest, just call the same function again. Good use to loop through binary trees or even directories on the computer!
We also did some unwinding, calculating the time it takes to loop through the recursive function (in quite a lazy way i must add! but hey we are lazy :-) ) doing some unwinding certainly have to be careful and not forget about adding time it took previously,
looks like term test 1 is coming up this friday, i don't think it'll be too brutal considering most of the things is about induction and the principle of well ordering, which shouldn't be too brutal, as i only had some problems with A1 #2 (although i do admit after seeing the solution for it, we were thinking too complicated....)
looking past that, we also try to do recursive functions in code, i personally don't know python, and am more familiar with java and the other programming languages, but using recursion in code is pretty neat, although, not every requires recursion as it does take up quite a heap of memory space, going forward once then backwards to output the answer. Recursion quite easy and simple, define a basecase, then for the rest, just call the same function again. Good use to loop through binary trees or even directories on the computer!
We also did some unwinding, calculating the time it takes to loop through the recursive function (in quite a lazy way i must add! but hey we are lazy :-) ) doing some unwinding certainly have to be careful and not forget about adding time it took previously,
looks like term test 1 is coming up this friday, i don't think it'll be too brutal considering most of the things is about induction and the principle of well ordering, which shouldn't be too brutal, as i only had some problems with A1 #2 (although i do admit after seeing the solution for it, we were thinking too complicated....)
Subscribe to:
Comments (Atom)
