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.
Friday, December 5, 2008
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).
Monday, September 29, 2008
Subscribe to:
Posts (Atom)