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.
Friday, October 17, 2008
More midterm thoughts
It has been a pretty crazy week and the upcoming week promises to be even worse. I'm finding the new material to be pretty confusing and will have to start reviewing the lecture slides more often. Today's lecture wasn't very clear to me, however that is probably due to how tired I was since I could barely keep my eyes open. I'd like to thank my CSC207 assignment for this. Unfortunately my other courses haven't left me with much time to spend on CSC236 and I know this is going to come back and hurt me in the next few weeks. Assignment 2 is worrying me but its going to have to wait as I have my STA247 and MAT223 midterms next week and they are worth 25% and 30% respectively. I really can't wait until November where I will have a bit of downtime and be able to catch up in the courses I'm falling behind in.
On an unrelated note, the exam schedule was released yesterday and I am not looking forward to that week. All my exams are back to back, something that has yet to happen to me in university. I guess I should start studying like a month in advance.
We also got the midterm back and I have to say I am pretty unhappy with how I did. I really wish I hadn't blanked out on the last question. I ended up getting 0/8 on the last question but with a remark I should be fine. I might edit this section in the future but now I've got lab so I'm going to cut this entry a little short.
On an unrelated note, the exam schedule was released yesterday and I am not looking forward to that week. All my exams are back to back, something that has yet to happen to me in university. I guess I should start studying like a month in advance.
We also got the midterm back and I have to say I am pretty unhappy with how I did. I really wish I hadn't blanked out on the last question. I ended up getting 0/8 on the last question but with a remark I should be fine. I might edit this section in the future but now I've got lab so I'm going to cut this entry a little short.
Sunday, October 12, 2008
Midterm Thoughts
I've got some downtime and its Sunday night, seems like a good time to write a blog entry. We had the midterm on Friday and I am very unhappy with how I did. I believe I got the Fibonnaci and variable k questions correct for near perfect however blanked out for the third question which I only had 10 minutes left to do. After trying a few solutions I ran out of time and settled for the old "I don't know how to answer this question.". Really sucks but I'm hoping I can still end up with at least a 65. The upcoming 3 weeks are going to be extremely busy for me with 2 very big midterms as well as a few assignments and smaller midterms. As a result I've been motivated to look at Problem Set #3 early and saw that it deals with unwinding. I mentioned this as a topic that I was having trouble with and am actually glad it is on the problem set so I will be able to become more familiar with it. Hopefully PS#4 will be quick though since I have a midterm on the due date :) In the meantime I might as well get started on #3..
Tuesday, October 7, 2008
A delayed update
So its been about 2 weeks since my last entry so I'll be making this one longer to cover what I have neglected. I left off after finishing Problem Set #1 and just starting the second one. It was much easier than I anticipated from my initial glance and I finished it without too much difficulty. Definitely gave me a nice confidence boost. Lectures have been going better since I switched over to the morning section and I'm rather happy with my decision. Keeping my sleeping habits more regulated is something I definitely have to work on and this is one way to motivate myself..
Assignment 1 was the next recent development and I found it fairly difficult. The first question was fairly straight forward once you conceptualized what was happening with the triangles and the most difficult part of it was translating your thoughts into a written proof. Number two was very confusing for me and I was happy to have my group members there to help explain it. Number three I also had some trouble with and will be going over both of them for this midterm. Hopefully by Friday I am completely comfortable with them.
Since my last entry we have covered a few new topics and a few haven't been entirely clear to me, something I definitely have to clear up before the upcoming midterm. Unwinding was pretty complicated to me and I'm sure I will be rereading those lecture slides many times before Friday. On a lighter note, I like that we are dealing with the Fibonacci sequence, its cool how we can prove things recursively, albeit somewhat complicated at times.
I remember I was the same in CSC165 around this time of the semester where I really stopped understanding a lot of things. It always takes a little while for my brain to get going and for concepts to really sink in at the beginning of a semester. I'm guessing this is mostly from lack of practice, as in 165 (as well as a few other courses) by mid semester I was fairly comfortable with most material and was learning things much quicker. Hopefully this semester will continue this trend as my classes are really just bombarding me with information right now. Really hope I can kick things in gear for this midterm, which is only my 2nd test this semester (the first being today in Linear Algebra..which I feel went well). Anyways besides that there has been no problem set this week so there isn't too much to talk about, I better get studying :)
Assignment 1 was the next recent development and I found it fairly difficult. The first question was fairly straight forward once you conceptualized what was happening with the triangles and the most difficult part of it was translating your thoughts into a written proof. Number two was very confusing for me and I was happy to have my group members there to help explain it. Number three I also had some trouble with and will be going over both of them for this midterm. Hopefully by Friday I am completely comfortable with them.
Since my last entry we have covered a few new topics and a few haven't been entirely clear to me, something I definitely have to clear up before the upcoming midterm. Unwinding was pretty complicated to me and I'm sure I will be rereading those lecture slides many times before Friday. On a lighter note, I like that we are dealing with the Fibonacci sequence, its cool how we can prove things recursively, albeit somewhat complicated at times.
I remember I was the same in CSC165 around this time of the semester where I really stopped understanding a lot of things. It always takes a little while for my brain to get going and for concepts to really sink in at the beginning of a semester. I'm guessing this is mostly from lack of practice, as in 165 (as well as a few other courses) by mid semester I was fairly comfortable with most material and was learning things much quicker. Hopefully this semester will continue this trend as my classes are really just bombarding me with information right now. Really hope I can kick things in gear for this midterm, which is only my 2nd test this semester (the first being today in Linear Algebra..which I feel went well). Anyways besides that there has been no problem set this week so there isn't too much to talk about, I better get studying :)
Wednesday, September 24, 2008
The Beginning
So I have finally gotten around to making my Slog. Honestly, it still feels like school just started, I am always so slow getting used to it again. My initial impressions of the course were that it seems like a natural extension of 165 which I enjoyed (once I got the hang of it around mid semester). Unfortunately, everything I learned last year has receded into the back of my mind and only now is starting to come back to me. At first I actually found many of the proofs to be quite difficult and even simple induction has been giving me trouble just from lack of practice. Last year I was the same and it took me until October to really get back in the swing of things. Definitely something I have to work on this term (the fact that this slog is being written is a step in the right direction I guess?).
Although I am registered in the morning lecture, for the first two weeks I had to attend the night time lectures from sleeping in accidentally on both Mondays, however after attending the morning lectures for the first time this week I really feel I got far more out of them. The 3 hours can really get to me after a long day and I find that by hour 2 I simply am not focused at all. So for the remainder of the semester I will be going to the morning lectures; despite the joys that come along with morning commuting. Plus this way I have Thursdays off :)
This year is starting to scare me, all of my classes are harder than last semester and I am expected to really do a fair amount of learning on my own in a short amount of time (like learn Java in CSC207). CSC236 seems to be following this pattern, seeming mostly like an extension of 165. Fortunately that's fine by me and I think this will be my favourite class of the semester. I finished Problem Set#1 with a fair amount of difficulty and was really uncomfortable with my solution to the second question. Hopefully the second one goes better. A friend of mine looked over it with me and said it looks easy, however I am not inclined to agree. Time for me to get started.
Although I am registered in the morning lecture, for the first two weeks I had to attend the night time lectures from sleeping in accidentally on both Mondays, however after attending the morning lectures for the first time this week I really feel I got far more out of them. The 3 hours can really get to me after a long day and I find that by hour 2 I simply am not focused at all. So for the remainder of the semester I will be going to the morning lectures; despite the joys that come along with morning commuting. Plus this way I have Thursdays off :)
This year is starting to scare me, all of my classes are harder than last semester and I am expected to really do a fair amount of learning on my own in a short amount of time (like learn Java in CSC207). CSC236 seems to be following this pattern, seeming mostly like an extension of 165. Fortunately that's fine by me and I think this will be my favourite class of the semester. I finished Problem Set#1 with a fair amount of difficulty and was really uncomfortable with my solution to the second question. Hopefully the second one goes better. A friend of mine looked over it with me and said it looks easy, however I am not inclined to agree. Time for me to get started.
Subscribe to:
Comments (Atom)