I am having some troubles stating the loop invariant, like the example we had during Wednesday's (Oct. 29th) lecture. For the function counter, how we worked out its loop invariant to be: a and b \in N, and 7*m + n = 7*a_i + b_i + c_i? I think I know why a and b has to be natural numbers, but for the latter part, the equation, I really didn't get it. Did we use the trail and error, or there is a systematic way for us to find the loop invariant for any while loops and for loops?
I know the casual defination for the loop invariant is that any variable or relationship that is unchanged during the loop's execution. However, will that just be the loop's content itself?
Friday, December 5, 2008
Week 7
Assignment 2 is so hard!
Although question 1 is from assignment 1, I still didn't get it this time. The only part of this question that I felt confident about is I managed to show that if a ternary tree has n nodes, there will be (2*n + 1) positions available to add a new node onto the tree. Although I didn't include that into my solution to question 1 since I think it is kind of irrelevant to the problem, I will prove it here.
P(n): if a ternary tree has n nodes, there will be (2*n + 1) positions on the tree available to add a new node.
Claim: \forall n \in N, P(n).
Proof: Base Case: For n = 0, the tree is the empty tree and there is only one position available to add a new node, namely the root. Since 1 = 2*0 + 1, P(0) is true.
Induction Step: assume n \in N and P(n) is true, that is (2*n + 1) positions are available to be added for a ternary tree with n nodes. To add a new node, note that it will take up one old position but itself will open up three new positions for a newer node to be add. Thus, from n to (n + 1), 2 more positions are created. Since 2*n + 1 + 2 = 2*(n + 1) + 1, P(n + 1) is true.
So \forall n \in N, P(n) => P(n + 1).
Thus, \forall n \in N, P(n).
That is everything. Hope the next assignment and the coming test won't be that hard.
Although question 1 is from assignment 1, I still didn't get it this time. The only part of this question that I felt confident about is I managed to show that if a ternary tree has n nodes, there will be (2*n + 1) positions available to add a new node onto the tree. Although I didn't include that into my solution to question 1 since I think it is kind of irrelevant to the problem, I will prove it here.
P(n): if a ternary tree has n nodes, there will be (2*n + 1) positions on the tree available to add a new node.
Claim: \forall n \in N, P(n).
Proof: Base Case: For n = 0, the tree is the empty tree and there is only one position available to add a new node, namely the root. Since 1 = 2*0 + 1, P(0) is true.
Induction Step: assume n \in N and P(n) is true, that is (2*n + 1) positions are available to be added for a ternary tree with n nodes. To add a new node, note that it will take up one old position but itself will open up three new positions for a newer node to be add. Thus, from n to (n + 1), 2 more positions are created. Since 2*n + 1 + 2 = 2*(n + 1) + 1, P(n + 1) is true.
So \forall n \in N, P(n) => P(n + 1).
Thus, \forall n \in N, P(n).
That is everything. Hope the next assignment and the coming test won't be that hard.
Week 6
I think the Master Therom for divide and conquer is so complicated. It has a lots of parameters (like a, b l) and conditions (like equal piece division), and the asymptote bounds generated by it is complicated too. Hope we don't have to memorize the whole formula in a test or exam.
One excited stuff: I got perfect on my term test 1! Although term test 1 is more like the stuff we did in CSC165, I am still happy about that, and should study even harder next time to keep the record, I guess.
One excited stuff: I got perfect on my term test 1! Although term test 1 is more like the stuff we did in CSC165, I am still happy about that, and should study even harder next time to keep the record, I guess.
Week 5
In the lecture on Oct 6th, we worked out a closed form for the function:
0, if n = 0
H(n) = { 2, if n = 1
3*H(n - 1) - 2*H(n - 2), if n > 1
which is H(n) = 2^(n + 1) - 2. Here is a proof of this formula by complete induction.
P(n): the closed form for the given function above is H(n) = 2^(n + 1) - 2.
Claim: \forall n \in N, P(n).
Proof: assume n \in N and P(0) /\ P(1) /\.../\P(n - 1) are true. Then either n <= 1 or n > 1.
Case 1: n <= 1. For n = 0, H(0) = 2^(0 + 1) - 2 = 2 - 2 = 0 which satisfies the defination of H(n) when n = 0. For n = 1, H(1) = 2^(1 + 1) - 2 = 4 - 2 = 2 which also satisfies the defination for n = 1. So H(0) and H(1) are true.
Case 2: n >= 1. According to the defination of H(n), H(n) = 3*H(n - 1) - 2*H(n - 2) = 3*(2^(n - 1 + 1) - 2) - 2*(2^(n - 2 + 1) - 2) = 3*2^n - 6 - 2*2^(n - 1) + 4 = 3*2^n - 2^n - 2 = 2*2^n - 2 = 2^(n + 1) - 2 which is the closed form for H(n).
So \forall n \in N, P(0) /\ P(1) /\.../\ P(n - 1) => P(n)
Thus, \forall n \in N, P(n).
0, if n = 0
H(n) = { 2, if n = 1
3*H(n - 1) - 2*H(n - 2), if n > 1
which is H(n) = 2^(n + 1) - 2. Here is a proof of this formula by complete induction.
P(n): the closed form for the given function above is H(n) = 2^(n + 1) - 2.
Claim: \forall n \in N, P(n).
Proof: assume n \in N and P(0) /\ P(1) /\.../\P(n - 1) are true. Then either n <= 1 or n > 1.
Case 1: n <= 1. For n = 0, H(0) = 2^(0 + 1) - 2 = 2 - 2 = 0 which satisfies the defination of H(n) when n = 0. For n = 1, H(1) = 2^(1 + 1) - 2 = 4 - 2 = 2 which also satisfies the defination for n = 1. So H(0) and H(1) are true.
Case 2: n >= 1. According to the defination of H(n), H(n) = 3*H(n - 1) - 2*H(n - 2) = 3*(2^(n - 1 + 1) - 2) - 2*(2^(n - 2 + 1) - 2) = 3*2^n - 6 - 2*2^(n - 1) + 4 = 3*2^n - 2^n - 2 = 2*2^n - 2 = 2^(n + 1) - 2 which is the closed form for H(n).
So \forall n \in N, P(0) /\ P(1) /\.../\ P(n - 1) => P(n)
Thus, \forall n \in N, P(n).
Week 4
I don't quite understand the "Zero-pair free binary strings" example given in class on Oct. 1st. It says:
def zpf(n):
if n == 0: #return the number of empty BS that do not have pairs of adjacent zeros.
if n == 1: #return the number of length one BS that do not have pairs of adjacent zeros.
else: #how many strings of length n, in terms of n - 1 and n - 2?
What does the last sentence mean? Does it mean that the strings of length n equals can be represented by the strings of length (n - 1) and (n - 2)? If so, how?
The example we had in class was:
00 and 10 in terms of n - 2
01 and 11 in terms of n - 1
That's even more confusing. Does it mean that if the string has length n ends with 00 or 10, the number of zero-free pairs equals that has a length (n - 2), and same argument for strings ends with 01 or 11? If so, why this is true?
I guess I'll look through the textbook to see if there is a solution to my question.
def zpf(n):
if n == 0: #return the number of empty BS that do not have pairs of adjacent zeros.
if n == 1: #return the number of length one BS that do not have pairs of adjacent zeros.
else: #how many strings of length n, in terms of n - 1 and n - 2?
What does the last sentence mean? Does it mean that the strings of length n equals can be represented by the strings of length (n - 1) and (n - 2)? If so, how?
The example we had in class was:
00 and 10 in terms of n - 2
01 and 11 in terms of n - 1
That's even more confusing. Does it mean that if the string has length n ends with 00 or 10, the number of zero-free pairs equals that has a length (n - 2), and same argument for strings ends with 01 or 11? If so, why this is true?
I guess I'll look through the textbook to see if there is a solution to my question.
Week 3
I am a little bit behind, but here is the proof of the uniqueness of quotient and remainder Prof. Heap mentioned in last Friday's (Sept 19's) class.
P(m): \forall n \in N\{0}, if \exists q and r \in N such that m = q*n + r and 0 <= r < n, then q and r are unique.
Claim: \forall m \in N, P(m).
Proof (by contradiction): assume m \in N. First we know that by the Principle of Well-Ordering, the set R = {r \in N \exists q \in N, m = q*n + r} has a least element, call it r_1 and the q corresponding to this r_1 is q_1. Then m = q_1*n + r_1. If q_1 and r_1 are unique, then there exist a pair q_2 and r_2 such that m = q_2*n + r_2 and 0 <= r_2 < m =" q_1*n" r_1 =" q_2*n"> r_1. Rearrange the above equation, we get (q_1 - q_2)*n = r_2 - r_1 > 0. So q_1 > q_2. Say q_1 = q_2 + k where k is some natural number greater than 0. Then m = q_1*n + r_1 = (q_2 + k) *n + r_1 = q_2*n + (r_1 + k*n) = q_2*n + r_2. So r_2 = r_1 + k*n > n, contradicts to that 0 <= r_2 < n. So q_1 and r_1 are unique.
So \forall m \in N, P(m).
P(m): \forall n \in N\{0}, if \exists q and r \in N such that m = q*n + r and 0 <= r < n, then q and r are unique.
Claim: \forall m \in N, P(m).
Proof (by contradiction): assume m \in N. First we know that by the Principle of Well-Ordering, the set R = {r \in N \exists q \in N, m = q*n + r} has a least element, call it r_1 and the q corresponding to this r_1 is q_1. Then m = q_1*n + r_1. If q_1 and r_1 are unique, then there exist a pair q_2 and r_2 such that m = q_2*n + r_2 and 0 <= r_2 < m =" q_1*n" r_1 =" q_2*n"> r_1. Rearrange the above equation, we get (q_1 - q_2)*n = r_2 - r_1 > 0. So q_1 > q_2. Say q_1 = q_2 + k where k is some natural number greater than 0. Then m = q_1*n + r_1 = (q_2 + k) *n + r_1 = q_2*n + (r_1 + k*n) = q_2*n + r_2. So r_2 = r_1 + k*n > n, contradicts to that 0 <= r_2 < n. So q_1 and r_1 are unique.
So \forall m \in N, P(m).
Week 2
The postage problem we did in class on Sept 19th used complete induction to prove. Here the same problem is proved by simple induction.
P(n): postage of n cents can be formed with 4- and 5-cent stamps.
Claim: \forall n \in N, n >= 12 => P(n).
Proof:
Base Case: for n = 12, 12-cent postage can be made by using three 4-cent stamps. So P(12) is true.
Induction Step: assume n \in N and n >= 12. Also assume P(n) is true, that is postage of n cents can be made by using 4- and 5-cent stamps. Then either n has at least one 4-cent stamp or n doesn't have any 4-cent postage.
Case 1: n has at least one 4-cent stamp. Then for (n + 1) postage, we can exchange that 4-cent stamp to a 5-cent stamp to get one cent more postage. So P(n + 1) is true in this case.
Case 2: n has no 4-cent stamp. Then n must have at least three 5-cent stamps, since 15 is the next natural number after 12 which is a multiple of 5. To get one more postage, we can simply exchange three 5-cent stamps (15 cents) to four 4-cent stamps (16 cents). So P(n + 1) is also true in this case.
Thus, P(n + 1) is true.
So \forall n \in N, (n >= 12 and P(n) ) => P(n + 1)
Therefore, \forall n \in N, n >= 12 => P(n).
P(n): postage of n cents can be formed with 4- and 5-cent stamps.
Claim: \forall n \in N, n >= 12 => P(n).
Proof:
Base Case: for n = 12, 12-cent postage can be made by using three 4-cent stamps. So P(12) is true.
Induction Step: assume n \in N and n >= 12. Also assume P(n) is true, that is postage of n cents can be made by using 4- and 5-cent stamps. Then either n has at least one 4-cent stamp or n doesn't have any 4-cent postage.
Case 1: n has at least one 4-cent stamp. Then for (n + 1) postage, we can exchange that 4-cent stamp to a 5-cent stamp to get one cent more postage. So P(n + 1) is true in this case.
Case 2: n has no 4-cent stamp. Then n must have at least three 5-cent stamps, since 15 is the next natural number after 12 which is a multiple of 5. To get one more postage, we can simply exchange three 5-cent stamps (15 cents) to four 4-cent stamps (16 cents). So P(n + 1) is also true in this case.
Thus, P(n + 1) is true.
So \forall n \in N, (n >= 12 and P(n) ) => P(n + 1)
Therefore, \forall n \in N, n >= 12 => P(n).
Subscribe to:
Posts (Atom)