Wednesday 5 December 2012
Nov 24 - 30 update
It's almost the end of the term, and finally I've done the final assignment for csc236 :D. I also posted tutorial about the background of the question, if it helps out anyone of you, I feel very happy to know that. Again sorry for not posting the tutorial earlier like I promised, my hand get swallow to the point I can't type or write anything, and it's been in bad shape. As we are all concern, the finals are coming :D. I hope the final for this course is testing stuff that is taught in the lecture, and mostly are the stuff that at least get talk about in the tutorial, as it will be easier to study for them. I hope all of you do good in the finals, and I mean all of your finals. That's it for this update, thanks for reading.
Friday 30 November 2012
Tutorial 2 repost
Sorry I deleted my tutorial 2 by mistake, so I have to type all those stuff again... Since my original post is almost 2 pages long, I'm going to short form this tutorial, since I got 2 more assignments coming up due last that 2 and 4 days and I'll busying finishing those, please understand...
This tutorial talks about the concept behind Q2 of our a3
If you are given a loop, and pre condition, prove proof it will terminate
First thing, This Q is actually 2 part Q: you have to prove partial correctness AND termination. Proof either one of those will not be enough.
For partial correctness, come up with a loop invariant, loop invariant is a condition statement that stays true throughout the whole loop as long as it is running. Then, assume the pre condition is true, proof that loop invariant is true before the first iterate occurs. After that, come up with a P(i) that is your loop invariant + pre condtion. Then proof P(i) by simple induction. first step proof P(i). When that's simple, that's exactly the proof for loop invariant is true before the first iterate occurs. Then we have to prove P(i+1). In order to do that, come up with a IH where assume i belongs arb Natural Number and P(i) holds, then proof the whole thing to get P(i+1), then P(i) => (P+1), which by simple induction, partial correctness is proved.
Now for Termination. We don't have to actually write induction all the time, All we have to do is assume the loop invariant is true, trace through the loop and show it eventually terminates. that's all.
Sorry for the simplified version, again sorry and please understand...
That's all, good luck on a3Q
This tutorial talks about the concept behind Q2 of our a3
If you are given a loop, and pre condition, prove proof it will terminate
First thing, This Q is actually 2 part Q: you have to prove partial correctness AND termination. Proof either one of those will not be enough.
For partial correctness, come up with a loop invariant, loop invariant is a condition statement that stays true throughout the whole loop as long as it is running. Then, assume the pre condition is true, proof that loop invariant is true before the first iterate occurs. After that, come up with a P(i) that is your loop invariant + pre condtion. Then proof P(i) by simple induction. first step proof P(i). When that's simple, that's exactly the proof for loop invariant is true before the first iterate occurs. Then we have to prove P(i+1). In order to do that, come up with a IH where assume i belongs arb Natural Number and P(i) holds, then proof the whole thing to get P(i+1), then P(i) => (P+1), which by simple induction, partial correctness is proved.
Now for Termination. We don't have to actually write induction all the time, All we have to do is assume the loop invariant is true, trace through the loop and show it eventually terminates. that's all.
Sorry for the simplified version, again sorry and please understand...
That's all, good luck on a3Q
Tutorial 4
This will be the last tutorial for a3, and is for Q4
Since the basic concept of this Q is similar to a2, this will be a short one, since I don't want to any waste too much time read similar concept
So in the Q, we are given pre condition and post condition, we are asked to prove that if the precondition is satisfie d, then your algorithm terminates and satisfie d the post-condition
What we want to do, similar to Q2, of course is to come up with a loop invariant! Question get so much easier with a loop invariant, whether you use it in your actual proof or not.
All you want to do it Assume the pre-condition is true, then prove that your loop invariant is true. Some approach maybe prove that invariant holds before the first loop is executed. I found that this is the easiest case to do it.
Then after proved that our loop invariant is true, now we assume the loop terminates and use the loop invariant to prove after it terminates, the post condition still holds. This is the different part from Q2, we can just assume the loop will terminate instead of proving it because we are given post condition, which post condition only stays true to those that are after the loop terminates. This implies the loop will eventually terminates, which is stupid to prove it terminates. If you still want to do it, be my guest, not like you are going to get extra marks but extra work, so why bother?
After you use loop invariant to prove postcondition, then you're all set, but what about the steps? Well, In order to prove something, aren't we always use induction? I'm going to use simple induction, where P(i) is the loop invariant + pre condition. The base case you may want to use something that terminate the loop instantly so that you can show the post condition show right away. for P(i+1), the IH should be i belong arb Natural Number and P(i) holds, and it's is the same procedure: Assume the loop will terminate, then use your loop invariant to proof your post condition. After you proof P(i) and P(i+1), then you proof the whole question by simple induction
I hope that help you with your a3, and good luck everyone!
Since the basic concept of this Q is similar to a2, this will be a short one, since I don't want to any waste too much time read similar concept
So in the Q, we are given pre condition and post condition, we are asked to prove that if the precondition is satisfie d, then your algorithm terminates and satisfie d the post-condition
What we want to do, similar to Q2, of course is to come up with a loop invariant! Question get so much easier with a loop invariant, whether you use it in your actual proof or not.
All you want to do it Assume the pre-condition is true, then prove that your loop invariant is true. Some approach maybe prove that invariant holds before the first loop is executed. I found that this is the easiest case to do it.
Then after proved that our loop invariant is true, now we assume the loop terminates and use the loop invariant to prove after it terminates, the post condition still holds. This is the different part from Q2, we can just assume the loop will terminate instead of proving it because we are given post condition, which post condition only stays true to those that are after the loop terminates. This implies the loop will eventually terminates, which is stupid to prove it terminates. If you still want to do it, be my guest, not like you are going to get extra marks but extra work, so why bother?
After you use loop invariant to prove postcondition, then you're all set, but what about the steps? Well, In order to prove something, aren't we always use induction? I'm going to use simple induction, where P(i) is the loop invariant + pre condition. The base case you may want to use something that terminate the loop instantly so that you can show the post condition show right away. for P(i+1), the IH should be i belong arb Natural Number and P(i) holds, and it's is the same procedure: Assume the loop will terminate, then use your loop invariant to proof your post condition. After you proof P(i) and P(i+1), then you proof the whole question by simple induction
I hope that help you with your a3, and good luck everyone!
Tutorial 3
This tutoria is for the concept of Q2 from a3
I don't have an example on mind right now so I'm just going to talk about the general procedure instead of doing example for this tutorial
For Q that given you the precondtion and ask you to come up with a loop invariant and prove for termination First there is 2 parts the question: It is actually asking you to prove 1)partial correctness and 2) termination. Notice I said and, not or, so you have to prove BOTH of them in order to prove it terminates.
For partial correctness part. First thing you want to come up is come up a loop invariant. Loop invariant is a condition statement which while the loop is still running, the statement condition is always true. If some sort of part your loop invariant is false(excluding termination), then you may want to think again about your loop invariant. Finding loop invariant is always the most tricky part of the question. Sometime it's so oblivious you don't have to trace through to see it, while other are the opposite. I went to the prof during office and ask if there's any general formula to find a loop invariant, and the answer is no. So be patient while finding it.
Once you find the loop invariant, you may want to prove the loop condition before the first loop being executed. This ensures that before the loop execute, your loop condition holds, or else your loop invariant is wrong.
Once you did that, now you may want to define P(i), where i is the time of iteration. And you may want to make the P(i) be the loop invariant you come up with plus pre condition. Once you set up though, you may want to set up a simple induction.
So for base case, it's always easier to make i = 0, as it is just the loop before it got executed the first time.
For P(i +1), you want want to get a IH that is similar to this format:
Assume i is a arb Natural Number and P(i) is true
Then go ahead and solve the P(i+1)
After you finish the simple induction, you have completed the partial correctness part, there's still the termination part...
To prove termination, Since we are given the loop will run and loop invariant is true, now what we want to do it that reverse the condition of the while loop (or any main loop that the program runs based on), ex (while x <y), you may want to make it (while x>=y). In here, how to do it is up to you, either induction or not, as long as you can show the loop will eventually terminates, that's what matters.
I hope this tutorial clears something out. Good luck on your a3!
I don't have an example on mind right now so I'm just going to talk about the general procedure instead of doing example for this tutorial
For Q that given you the precondtion and ask you to come up with a loop invariant and prove for termination First there is 2 parts the question: It is actually asking you to prove 1)partial correctness and 2) termination. Notice I said and, not or, so you have to prove BOTH of them in order to prove it terminates.
For partial correctness part. First thing you want to come up is come up a loop invariant. Loop invariant is a condition statement which while the loop is still running, the statement condition is always true. If some sort of part your loop invariant is false(excluding termination), then you may want to think again about your loop invariant. Finding loop invariant is always the most tricky part of the question. Sometime it's so oblivious you don't have to trace through to see it, while other are the opposite. I went to the prof during office and ask if there's any general formula to find a loop invariant, and the answer is no. So be patient while finding it.
Once you find the loop invariant, you may want to prove the loop condition before the first loop being executed. This ensures that before the loop execute, your loop condition holds, or else your loop invariant is wrong.
Once you did that, now you may want to define P(i), where i is the time of iteration. And you may want to make the P(i) be the loop invariant you come up with plus pre condition. Once you set up though, you may want to set up a simple induction.
So for base case, it's always easier to make i = 0, as it is just the loop before it got executed the first time.
For P(i +1), you want want to get a IH that is similar to this format:
Assume i is a arb Natural Number and P(i) is true
Then go ahead and solve the P(i+1)
After you finish the simple induction, you have completed the partial correctness part, there's still the termination part...
To prove termination, Since we are given the loop will run and loop invariant is true, now what we want to do it that reverse the condition of the while loop (or any main loop that the program runs based on), ex (while x <y), you may want to make it (while x>=y). In here, how to do it is up to you, either induction or not, as long as you can show the loop will eventually terminates, that's what matters.
I hope this tutorial clears something out. Good luck on your a3!
Sunday 25 November 2012
Tutorial 1
So for a3 Q1, I'm pretty sure everyone knows it's about DFSA :p. I mean, every the question says itself. So what is DFSA? DFSA stands for DETERMINISTIC FINITE STATE AUTOMATA. Let me state it an easy way, it is just like playing a board game. You start from the beginning (initial state is the term), In our sake, you have 2 choice, left (0) and right (1). You are already given a path to walk already (ex: 10001000111). So you walk along the board. If you go to the pre-determined goal after finish walking all the indices, then you win (accepting state). If you can't, then you lose (rejected). This sounds simple right? I have some struggle with it first though. Because most of the question, you are not given the board, only the sequence. As far as the simple sequence go, it is pretty straight forward. However it will get messy sometimes.
Notice that this DFSA is just like Markov Chain from sta247 (I'm pretty sure most of us have to take it. If you aren't, then I'm really sorry, because I can't draw here.)
Let's do an example, 100
Whate you have to do it is:
you start on Initial state(q0)
Then you in order to advance, you look at the first element, it is one, so you make (q1) by using an arrow to indicate it transit by 1.
So what happen to 0? It will have another branch of to (q2) which transit by 0. However, we can clearly see that if you enter this q2, it will be in rejected by default, since there is no way you can get to 1 by going that way (think of it as a dead end). We have a special name for this sort of branch, and it's call death state. Usually for cleaness, we will not draw death state on the graph (board). Onto next 0, same steps, 2 branches, (q3) by transit by 0, (q4) transit by 1, which (q4) is a death end. Onto last element 0. For this, since we are already in (q3), which is transit by 0, think of (q3) is equal to 0, there is not point of advacing to the next path, since (q3) is already 0, we can just make a big U turn and go back to (q3) by transit 0. For transit 1, we branch out to (q4) which is a death state. Notice I can't do U turn for 1 is because think of (q3) is 0, 0 =/= 1, so it can't loop back. So we are at the end, and (q3) will be our accepting state (goal). If you land on anything other than (q3), it is by default going to reject.
Let's go through the definition of symbols of DFSA. So it looks like this:
DFSA = (Q, S ,A , s, F)
where Q is the finite set of states(i.e how many steps it takes to go to the accepting state.)(ex: {q1,q2,q3}), S is the finite alphabet(i.e, the character contained in this sequence.)(ex: {0,1}),
A is the transition function(Q*S),
s is the Initial State (q0)
F is the set of accepting state (Whatever your accepting state is)
Last but not least:
The regular expression of DFSA is usually how the Question from a test look like,
L1 = {x belong to {0, 1} | x has an odd number of 0s and an odd number of 1s} (from textbook ex7.12)
So what does it mean in the {}?
For those who are new to this sort of expression, it simply means that we execute the condition before the "|" , however, that condition must to follow the condition after the "|". So in the example, it simply means that we have to find a x which only contains 0 and 1, and the x must follow the following condition: x has an odd number of 0s and an odd number of 1s.
I hope this helped you clarify any unclear concepts in your mind. Hope you all do good in the course, and see you next time :D.
Notice that this DFSA is just like Markov Chain from sta247 (I'm pretty sure most of us have to take it. If you aren't, then I'm really sorry, because I can't draw here.)
Let's do an example, 100
Whate you have to do it is:
you start on Initial state(q0)
Then you in order to advance, you look at the first element, it is one, so you make (q1) by using an arrow to indicate it transit by 1.
So what happen to 0? It will have another branch of to (q2) which transit by 0. However, we can clearly see that if you enter this q2, it will be in rejected by default, since there is no way you can get to 1 by going that way (think of it as a dead end). We have a special name for this sort of branch, and it's call death state. Usually for cleaness, we will not draw death state on the graph (board). Onto next 0, same steps, 2 branches, (q3) by transit by 0, (q4) transit by 1, which (q4) is a death end. Onto last element 0. For this, since we are already in (q3), which is transit by 0, think of (q3) is equal to 0, there is not point of advacing to the next path, since (q3) is already 0, we can just make a big U turn and go back to (q3) by transit 0. For transit 1, we branch out to (q4) which is a death state. Notice I can't do U turn for 1 is because think of (q3) is 0, 0 =/= 1, so it can't loop back. So we are at the end, and (q3) will be our accepting state (goal). If you land on anything other than (q3), it is by default going to reject.
Let's go through the definition of symbols of DFSA. So it looks like this:
DFSA = (Q, S ,A , s, F)
where Q is the finite set of states(i.e how many steps it takes to go to the accepting state.)(ex: {q1,q2,q3}), S is the finite alphabet(i.e, the character contained in this sequence.)(ex: {0,1}),
A is the transition function(Q*S),
s is the Initial State (q0)
F is the set of accepting state (Whatever your accepting state is)
Last but not least:
The regular expression of DFSA is usually how the Question from a test look like,
L1 = {x belong to {0, 1} | x has an odd number of 0s and an odd number of 1s} (from textbook ex7.12)
So what does it mean in the {}?
For those who are new to this sort of expression, it simply means that we execute the condition before the "|" , however, that condition must to follow the condition after the "|". So in the example, it simply means that we have to find a x which only contains 0 and 1, and the x must follow the following condition: x has an odd number of 0s and an odd number of 1s.
I hope this helped you clarify any unclear concepts in your mind. Hope you all do good in the course, and see you next time :D.
Oct 18-25 weekly update
Sorry for not updating anything lately, My right hand has some issues that make it so painful I cannot type or write. My hand is recovered now and I can type again :D. I know I promise the tutorials, what I will do right now is to discuss the concept of each question of a3. However, if you are looking for solutions, then I suggest you leave right now, don't waste your time, I'm not going to write any answers for it. All I am going to do is to discuss the concept(as what I understand the question). Starting next post, thank you taking your time to read it.
Tuesday 6 November 2012
Oct 29- Nov 4 weekly update
Sorry for the late update, so many stuff has been going in my life... I got the test on mon... essay and quiz on tues.... worst of all my sister went to the hospital! Nothing major, but still thank god she's ok. Anyway, The week's stuff is kinda hard to catch up, I would appreciate though the test and the tutorial are not the same day so I can get a tutorial session to understand the stuff. And by next week (which is this week) I'm going to start my math analyst session, and share the solutions and problems I have during this course and anything related. Hope this benefits you or you can correct me. That's all for today, see you in the next update.
Subscribe to:
Posts (Atom)