Well I just wrote the third test and completely imploded. I actually studied a fair bit however my brain just went completely blank on the first and second questions. The first one took me forever and I'm pretty sure I got it wrong as I ignored the typo until like half way through, tried changing it and just ended up getting really confused even though it wasn't actually that difficult. Then I did question 3 and by the time I got started on question 2 (which I'm fairly sure I could have answered correctly) I had so little time left that I just opted for the old "I cannot answer this question". Really disappointed with myself and wish I could just do it again. Oh well such is life, at least it will only be worth 6% with the amazing 236 marking scheme :)
This semester went by incredibly quickly and it still hasn't fully hit me that exams are next week. I'm really worried for every single class but cannot devote much time to either csc207 or csc236 since I have linear algebra (mat223) and stats (sta247) in the two days before. Honestly, I hated csc207 and stats (in my opinion two terribly designed courses), and feel that 236 was my favourite class. Unfortunately I was not able to devote as much time as I wanted to it and am still terrible with languages. Hopefully I will have enough time on Thursday to get a good grasp of the material and be able to get at least a semi decent mark on the exam.
Thanks for providing me with a somewhat enjoyable computer science course Danny, its been an interesting semester in csc236 at least. The course was quite refreshing when compared to my other courses and like csc165 last winter, it was my favourite course of the term. Hopefully I'll see you at some point next semester!
Friday, December 5, 2008
Tuesday, December 2, 2008
Problem Solving Session
A3 Q1
http://www.cdf.toronto.edu/~heap/236/f08/A3/a3.pdf
1. UNDERSTANDING THE PROBLEM
Since we have to prove program correctness, the first thing we have to develop is a loop invariant. Afterwards we have to show that the loop invariant holds true for the loop. Then we must prove partial correctness and then show termination.
2. DEVISING A PLAN
This problem is fairly similar to the multiplication program example in the textbook, so we will try to model our solution based on that somewhat. So we take a look at the program's loop and think about possible conditions that remain true before and after the loop. We know the pre and postconditions, so it is likely that invariant will contain at least some element of them.
3. CARRY OUT THE PLAN
The first thing we must do is find the loop invariant. The only one I could come up with is:
P(i): If the loop is executed at least i times then n = q_i*m + r_i.
I considered some other possibilities, such as negating the loop exit condition, however did not see a way to use this further in the proof.
We must prove this is the loop invariant:
Basis: Let i = 0.
Then q_0 = 0 and r_0 = n.
Then q_0*m + r_i = 0 + r_i = n
Then P(i)
Induction: Let j \in \N and assume that P(j) holds.
If m > r_j+1 then the loop doesn't execute and P(j+1) will be vaccuously true.
Otherwise r_j+1 = r_j - m and q_j+1 = q_j + 1.
Then r_j+1 + m*q_j+1 = (r_j - m) + (q_j + 1)
= r_j + m(-1 + q_j + 1)
= r_j + m*q_j
= n
Then P(j+1)
Thus P(i) \implies P(i+1) and P(i) is true by simple induction.
Now that we have the loop invariant, we must prove partial correctness and termination to show that the program is correct.
a) Partial Correctness:
Partial correctness is not very difficult to prove since we already proved our loop invariant. All that remains to be shown is the remaining part of the postcondition. We can model this solution on the Multiplication program's solution from Chapter 2 in the textbook.
P(i): Suppose the precondition holds. Then if quotRem(n,m) terminates, the
postcondition holds.
Assume the precondition holds and quotRem(n,m) terminates. Since it terminates,
the loop will be executed a finite number of times, lets call this natural
number 'k'. By the exit condition, m > r_k. m and r are natural numbers
by the precondition and m <= r_k-1 (must be true for the kth iteration of the loop to occur). Then r_k >= 0 since subtracting m from r_k-1 will never be less
than 0. Then 0 <= r_k < n =" q_k*m"> is decreasing.
Let k_i = r
Then k_i \in \N since r \in \N
Assume the loop is executed at least i+1 times.
Then k_i+1 = r - m
Then k_i+1 > k_i (since m cannot be 0 by the precondition)
Then the sequence is decreasing
Then P(i)
By the Principle of Well Ordering every set of decreasing natural numbers has a
smallest element. Then the sequence has a smallest element.
Therefore it is finite and the loop will terminate since an infinite set of
decreasing natural numbers is impossible.
We have now proven all elements necessary for this program's correctness and just need a concluding statement:
Then if quotRem(n,m) is called with arguments that satisfy the precondition,
it terminates, and when it does it satisfies the postcondition.
4. LOOKING BACK
Intuitively I can see that the program is correct and indeed carries out the division of numbers successfully. I am satisfied with my solution and have proved everything needed. There is no grey area that could allow for a loophole in the program's correctness. I don't think there are other ways to prove this program's correctness, unless you were able to come up with a unique loop invariant. The other parts of the proof are pretty mechanical and as such I feel confident that my answer is more than adequate.
http://www.cdf.toronto.edu/~heap/236/f08/A3/a3.pdf
1. UNDERSTANDING THE PROBLEM
Since we have to prove program correctness, the first thing we have to develop is a loop invariant. Afterwards we have to show that the loop invariant holds true for the loop. Then we must prove partial correctness and then show termination.
2. DEVISING A PLAN
This problem is fairly similar to the multiplication program example in the textbook, so we will try to model our solution based on that somewhat. So we take a look at the program's loop and think about possible conditions that remain true before and after the loop. We know the pre and postconditions, so it is likely that invariant will contain at least some element of them.
3. CARRY OUT THE PLAN
The first thing we must do is find the loop invariant. The only one I could come up with is:
P(i): If the loop is executed at least i times then n = q_i*m + r_i.
I considered some other possibilities, such as negating the loop exit condition, however did not see a way to use this further in the proof.
We must prove this is the loop invariant:
Basis: Let i = 0.
Then q_0 = 0 and r_0 = n.
Then q_0*m + r_i = 0 + r_i = n
Then P(i)
Induction: Let j \in \N and assume that P(j) holds.
If m > r_j+1 then the loop doesn't execute and P(j+1) will be vaccuously true.
Otherwise r_j+1 = r_j - m and q_j+1 = q_j + 1.
Then r_j+1 + m*q_j+1 = (r_j - m) + (q_j + 1)
= r_j + m(-1 + q_j + 1)
= r_j + m*q_j
= n
Then P(j+1)
Thus P(i) \implies P(i+1) and P(i) is true by simple induction.
Now that we have the loop invariant, we must prove partial correctness and termination to show that the program is correct.
a) Partial Correctness:
Partial correctness is not very difficult to prove since we already proved our loop invariant. All that remains to be shown is the remaining part of the postcondition. We can model this solution on the Multiplication program's solution from Chapter 2 in the textbook.
P(i): Suppose the precondition holds. Then if quotRem(n,m) terminates, the
postcondition holds.
Assume the precondition holds and quotRem(n,m) terminates. Since it terminates,
the loop will be executed a finite number of times, lets call this natural
number 'k'. By the exit condition, m > r_k. m and r are natural numbers
by the precondition and m <= r_k-1 (must be true for the kth iteration of the loop to occur). Then r_k >= 0 since subtracting m from r_k-1 will never be less
than 0. Then 0 <= r_k < n =" q_k*m"> is decreasing.
Let k_i = r
Then k_i \in \N since r \in \N
Assume the loop is executed at least i+1 times.
Then k_i+1 = r - m
Then k_i+1 > k_i (since m cannot be 0 by the precondition)
Then the sequence
Then P(i)
By the Principle of Well Ordering every set of decreasing natural numbers has a
smallest element. Then the sequence
Therefore it is finite and the loop will terminate since an infinite set of
decreasing natural numbers is impossible.
We have now proven all elements necessary for this program's correctness and just need a concluding statement:
Then if quotRem(n,m) is called with arguments that satisfy the precondition,
it terminates, and when it does it satisfies the postcondition.
4. LOOKING BACK
Intuitively I can see that the program is correct and indeed carries out the division of numbers successfully. I am satisfied with my solution and have proved everything needed. There is no grey area that could allow for a loophole in the program's correctness. I don't think there are other ways to prove this program's correctness, unless you were able to come up with a unique loop invariant. The other parts of the proof are pretty mechanical and as such I feel confident that my answer is more than adequate.
Thursday, November 27, 2008
A ton of studying ahead
It seems that the good times have ended. Exams, which seemed much further away last week than they do now, are right around the corner. This semester I am facing the worst exam schedule I've ever had and coupled with the fact that all of my courses will require a fair amount of time to study for, I'm getting really worried. I am quite behind in MAT223 and will have to teach myself a ton of material in the upcoming week. Furthermore I will be entering the STA247 exam with something like a 60, and seeing as how I have a significant amount of trouble with the material, I really feel I might be in jeopardy of failing. I started studying yesterday but I really feel I am going to have to devote my life until Dec 9 to studying. So be it, at least I can complain about it on this blog. On the upside, studying for Test 3 will just be another form of studying for the exam, so I don't really mind having it on the last day of school. So be it, at least I can complain about it on this blog.
On another note, we got our problem sets back and as predicted, I basically imploded on Problem set 5 with an awesome 0/10. Ah well, it appears I completely missed the point of the question. In retrospect I probably should have spent more time on it but so it goes sometimes. I'm a lot more confident in problem set 6 at least. Today I also looked over the problem solving exercise and was going to write up a solution, however this quickly turned into an act of futility as I failed at using the Wiki and lost motivation to continue. I took a look at all of the problems but ended up trying the SimpleCartography one. I'm not going to go into my current solution here since I should be posting it on the Wiki. Going to have to do that in between study sessions sometime next week. Hard to believe the semester is a week from being over, its really insane how fast the last 3 months flew by and how much (or how little depending on the context) I have accomplished since then. Let's just hope exams go well.
On another note, we got our problem sets back and as predicted, I basically imploded on Problem set 5 with an awesome 0/10. Ah well, it appears I completely missed the point of the question. In retrospect I probably should have spent more time on it but so it goes sometimes. I'm a lot more confident in problem set 6 at least. Today I also looked over the problem solving exercise and was going to write up a solution, however this quickly turned into an act of futility as I failed at using the Wiki and lost motivation to continue. I took a look at all of the problems but ended up trying the SimpleCartography one. I'm not going to go into my current solution here since I should be posting it on the Wiki. Going to have to do that in between study sessions sometime next week. Hard to believe the semester is a week from being over, its really insane how fast the last 3 months flew by and how much (or how little depending on the context) I have accomplished since then. Let's just hope exams go well.
Thursday, November 20, 2008
Things on the horizon
The past two weeks have been a nice break from everything, but things are about to go bad very soon. Exams are coming up and I am really worried. The workload is picking up again also, with 3 assignments due Monday, A3 being one of them of course, the other two being for STA247 and CSC207. I've looked over A3 a bit and will be doing most of it this Saturday and probably Monday with my group. I'm glad to say it doesn't look nearly as intimidating as A3 was. Lectures have gotten way more abstract lately with finite state automata and I will have to really devote some time to becoming familiar with these soon. Exams seem to be just on the horizon but I still have some time. Today I finished the last problem set with two buddies and ended up spending most of the day at school failing to do stats, then going home...and writing this blog entry. The problem set was certainly easier for me than the last one and having friends with me to clarify things was a big help as well. Problem set 5 was a definite screw up looking back on it now. Oh well, maybe I will end up getting some part marks. Anyways there isn't really much else going on right now, I'm off to use what little free time I have for some much needed relaxing :)
Friday, November 14, 2008
Some sort of break
So this is the first week in a long time where I actually don't have an assignment or test due in the next few days. I finished off the last horrible vestiges of my tests/assignments this Tuesday with my linear algebra quiz that in all honesty think I did fairly poorly on. Unfortunately I only had a day to study for it and missed a key part of the material. Nevertheless I'm fairly certain my mark will be 14/20, so things could be worse.
We got Test 2 handed back today and I am really happy with my mark. My final mark was 19/24 which is...about like 7 more then I was expecting. The fact that I'm not really as lost as I thought I was and that I can still come up with logical proofs for more complicated problems is a big relief. I don't think I will be leaving a question blank again anytime soon. Looking back on when I was writing it I thought I did extremely poorly and seeing that I was actually on the right track for every question is a big relief since I was beginning to feel really lost in this class. Doing the problem set has forced me to catch up on some of the material (although I'm fairly certain my solution for ps5 was just terribly terribly wrong) so I'm happy that I can start actually understanding what is going on. Although I've got a CSC207 exercise and STA247 problem set (I hate those things..) due Monday I'm going to try to catch up on all the reading for DFSA's so that come Monday I can have a better understanding of what is going on. Exams are coming up and with my horrible exam schedule (4 in a row) I have to really focus on learning the material now as essentially I'm going to have very little time to study after school ends.
We got Test 2 handed back today and I am really happy with my mark. My final mark was 19/24 which is...about like 7 more then I was expecting. The fact that I'm not really as lost as I thought I was and that I can still come up with logical proofs for more complicated problems is a big relief. I don't think I will be leaving a question blank again anytime soon. Looking back on when I was writing it I thought I did extremely poorly and seeing that I was actually on the right track for every question is a big relief since I was beginning to feel really lost in this class. Doing the problem set has forced me to catch up on some of the material (although I'm fairly certain my solution for ps5 was just terribly terribly wrong) so I'm happy that I can start actually understanding what is going on. Although I've got a CSC207 exercise and STA247 problem set (I hate those things..) due Monday I'm going to try to catch up on all the reading for DFSA's so that come Monday I can have a better understanding of what is going on. Exams are coming up and with my horrible exam schedule (4 in a row) I have to really focus on learning the material now as essentially I'm going to have very little time to study after school ends.
Saturday, November 8, 2008
The wave continues
Well the wave of assignments and midterms continues. I'm really starting to burn out and can't wait until next week when I will finally have a break (somewhat). The drop date just recently passed and I'm facing a lot of anxiety regarding my course and degree decisions. A recent new interest in investments has made me consider getting a major in Economics and a major in CS instead of doing just a specialist in CS. There are a number of reasons for this, however I really think its too early for me to decide yet. However I would really like to keep this option open and my choice of STA247 may impact this in the future. So when 'the wave' ends I definitely have to go see a guidance councilor and likely talk to the economics department.
Test 2 was just yesterday and I really don't think I did well. I've spent the last few days working on a CSC207 assignment and had to do most of my studying on Thursday. My friend Tushar decided to go to Danny's office hour and I figured I'd tag along. I'm glad I did because even though the material wasn't exactly on the test it definitely clarified a few things about mergesort. I thought my answers to #1 and #3 were somewhat hand wavey and I was unable to prove any sort of loop invariant for #3. However this time I decided to just write whatever I could rather then leave it blank. I figure if I can get at least some part marks then this test might not be so bad. My answer for #2 I think was fairly correct, however I think I should have used induction rather then simply explaining everything in english. We'll see once I get it back, looking back though I think I did terrible...hopefully I didn't totally implode.
Test 2 was just yesterday and I really don't think I did well. I've spent the last few days working on a CSC207 assignment and had to do most of my studying on Thursday. My friend Tushar decided to go to Danny's office hour and I figured I'd tag along. I'm glad I did because even though the material wasn't exactly on the test it definitely clarified a few things about mergesort. I thought my answers to #1 and #3 were somewhat hand wavey and I was unable to prove any sort of loop invariant for #3. However this time I decided to just write whatever I could rather then leave it blank. I figure if I can get at least some part marks then this test might not be so bad. My answer for #2 I think was fairly correct, however I think I should have used induction rather then simply explaining everything in english. We'll see once I get it back, looking back though I think I did terrible...hopefully I didn't totally implode.
Saturday, October 25, 2008
Lots of work
So its been incredibly hectic since my last entry. On October 20th I had a stats midterm, and on the 23rd I had a linear algebra midterm, so the problem set extension was very appreciated. Unfortunately Assignment 2 is due on Monday, along with a small assignment from CSC207 that's going to take me forever since I am sucking at Java. Plus there's a CSC207 midterm on Wednesday...and phase II of our project for Friday. Good times.
Anyways I've looked over A2 somewhat but haven't had much time to really put into it, those 2 midterms were pretty terrible. So far it looks pretty impossible, hopefully my group members will have some idea. Number 4 is the only one I really have any idea how to do so far. As for what we've been doing in lectures, I'm starting to get a bit lost. While I understand during lecture when it comes time to do it I often struggle. Alot of this is probably just because I haven't had much time for 236 lately, so hopefully I'll catch up soon.
Anyways I've looked over A2 somewhat but haven't had much time to really put into it, those 2 midterms were pretty terrible. So far it looks pretty impossible, hopefully my group members will have some idea. Number 4 is the only one I really have any idea how to do so far. As for what we've been doing in lectures, I'm starting to get a bit lost. While I understand during lecture when it comes time to do it I often struggle. Alot of this is probably just because I haven't had much time for 236 lately, so hopefully I'll catch up soon.
Subscribe to:
Comments (Atom)