Monday,
---------- Oct. 13, 2008
After talking about the correctness of recursive programs last week, we moved to iterative programs. The tricky part in codes with “for” and “while” loops is that you have to prove that the code eventually terminates; and when it does; it satisfies the postcondition.
So we might need to find a loop invariant first; something that demonstrates how the loop is progressing towards the goal. Then, we need to find a non-empty decreasing sequence of natural numbers to prove that the loop actually terminates. Finally, we use the information we gathered from the first and second part to conclude that if the preconditon holds then the postcondition is satisfied when the loop exists.
Assignment 2,
---------- Oct. 13, 2008
WOW! that was one hard assignment. I have to admit that although I started to read and think about the assignment a week ago, I did not do any real work till yesterday. The result? I was typing till 9:50 pm today.
Question 4 was okay because it is similar to the one we did in lecture (I hope so). Question 3 was fine. The sequence of G(n) was easy but I do not know why it took my partner and I a long time to figure it out. For question 2, I did exactly as we did in lecture; I found T(n), found its closed form, proved it holds for powers of 7, proved T(n) is non-decreasing, and finally squeezed non-powers of 7 between powers of 7. It was a long proof, but this is how I understood it in lecture and I could not risk trying some other method 5 hours before the assignment was due.
Question 1; oh what can I say. My partner and I used an approach which we thought was promising (we got T(n) = 3T(n-1) + other stuff). We wanted to push our formula further but we neither had the time nor the nerve, so we used a method that includes summation. I guess I should drop by Professor Danny's office and discuss that first formula with him; I am sure he will figure something out.
In conclusion, I have spent around, without the time my partner's time, around 17 hours working on this assignment, and I think this exceeds the weekly 8 hours for CSC236. I should have started earlier, and I should have given more credit to the difficulty of question 1. I really need to do well in the up-coming test because I think I will get 60 or something in this assignment.
Wednesday,
---------- Oct. 15, 2008
I could not make it to class today; but I checked the lecture and course notes. Professor Danny did another example of iterative correctness; this time with a tricky termination.
Friday,
---------- Oct. 17, 2008
We concluded out discussion about program correctness by doing an example of nested loops. The first impression I had was "Oh my God...that looks nasty." But Professor Danny broke the nest loop into an inner and an outer loop. Then he proved the inner one normally and then the outer one. Pretty simple, huh? I just love the way in Danny manages to break down the most complicated proofs into smaller, simpler, and familiar problems. But anyway I do not think I would like to see a double-loop question in the exam.
---------- Oct. 13, 2008
After talking about the correctness of recursive programs last week, we moved to iterative programs. The tricky part in codes with “for” and “while” loops is that you have to prove that the code eventually terminates; and when it does; it satisfies the postcondition.
So we might need to find a loop invariant first; something that demonstrates how the loop is progressing towards the goal. Then, we need to find a non-empty decreasing sequence of natural numbers to prove that the loop actually terminates. Finally, we use the information we gathered from the first and second part to conclude that if the preconditon holds then the postcondition is satisfied when the loop exists.
Assignment 2,
---------- Oct. 13, 2008
WOW! that was one hard assignment. I have to admit that although I started to read and think about the assignment a week ago, I did not do any real work till yesterday. The result? I was typing till 9:50 pm today.
Question 4 was okay because it is similar to the one we did in lecture (I hope so). Question 3 was fine. The sequence of G(n) was easy but I do not know why it took my partner and I a long time to figure it out. For question 2, I did exactly as we did in lecture; I found T(n), found its closed form, proved it holds for powers of 7, proved T(n) is non-decreasing, and finally squeezed non-powers of 7 between powers of 7. It was a long proof, but this is how I understood it in lecture and I could not risk trying some other method 5 hours before the assignment was due.
Question 1; oh what can I say. My partner and I used an approach which we thought was promising (we got T(n) = 3T(n-1) + other stuff). We wanted to push our formula further but we neither had the time nor the nerve, so we used a method that includes summation. I guess I should drop by Professor Danny's office and discuss that first formula with him; I am sure he will figure something out.
In conclusion, I have spent around, without the time my partner's time, around 17 hours working on this assignment, and I think this exceeds the weekly 8 hours for CSC236. I should have started earlier, and I should have given more credit to the difficulty of question 1. I really need to do well in the up-coming test because I think I will get 60 or something in this assignment.
Wednesday,
---------- Oct. 15, 2008
I could not make it to class today; but I checked the lecture and course notes. Professor Danny did another example of iterative correctness; this time with a tricky termination.
Friday,
---------- Oct. 17, 2008
We concluded out discussion about program correctness by doing an example of nested loops. The first impression I had was "Oh my God...that looks nasty." But Professor Danny broke the nest loop into an inner and an outer loop. Then he proved the inner one normally and then the outer one. Pretty simple, huh? I just love the way in Danny manages to break down the most complicated proofs into smaller, simpler, and familiar problems. But anyway I do not think I would like to see a double-loop question in the exam.
No comments:
Post a Comment