Proof of Lemma 3.4 (Course Notes):
Take T(n) = c if n = 1
2T(n/2) + dn if n > 1.
Then let P(i) be the predicate (i.e. the lemma)
P(i): "For each natural number n that is a power of 2 s.t. i <= long, T(n) = (2^i)T(n/(2^i)) + idn."
- In the base case (i = 0), the writer skips assuming arbitrary natural number n and skips checking whether that n is a power of 2 s.t. i <= logn, and instead immediately proves P(0), because it is clear that T(n) = (2^0)T(n/(2^0)) + (0)dn. I just wanted to make clear that since this is immediately obvious, I hope that the professor/TAs would also approve of this "skip".
Proof of Theorem 3.7 (Course Notes):
There exists a constant k >= 0 so that for all integers n >=2, T(n) <= knlogn.
I'm sure everyone likes having good intuition to reassure themselves that they can do a particular proof #0. Hence, I myself spend a lot of time searching for the "intuitive spark" for every interesting proof I encounter. Oftentimes you'd have to skip to "mathematical manipulation" part of the proof and see where you get stuck or what is obviously needed for the next step - then you can say: "Ah, so now that I know every part that is needed, I can see that we should choose ____ at the beginning" (i.e. now I have as much as I possibly get for an intuitive sense of the proof at this point in the mathematical evaluation/manipulation of the predicate).
So I searched for intuition here.
Basically, we have to apply Thm 3.5: "If n is a power of 2, T(n) = cn + dnlogn" to T(n), since it's the only thing we know about T(n)'s value in closed form.
Proof of a bound for recursive binary search
- Let's say we try to prove for all positive natural numbers n, there exists a c in the positive real numbers, such that T(n) >= clog(n) by complete induction.
- Then in the case that n > 1, we must choose a different c' in terms of c in clog(ceiling(n/2)), this from using the induction hypothesis on T(ceiling(n/2)). Both in class and in tutorial was this step skipped. Luckily (more likely than not they did know it), it was still correct to choose "c = 1", when:
1) it should be "Then there exists a positive real number c' such that T(n) >= c'log(n)."
and 2) "# Choose c' <= 1 if c > 1, and c' = c otherwise", which technically is c' <= 1, but more with more rigour and clarity (at least it is the least level of rigour to prove something to me).
Proof of a bound for MergeSort
- Proving a stronger claim shouldn't ever be something to "pull out of a hat". I hate pulling out of a hat, because it a sad beauty to withhold when you don't know how it works. Honestly, it is intuition that allows you to choose T(n) <= clog(n - 1) from T(n) <= clog(n) because you tried the latter and saw that subtracting 1 from n may actually help. It's akin to walking through a series of tunnels to reach the other side. When you find yourself in a dead end, you don't just turn 180 degrees and walk blindly back to the entrance; instead, while walking back you look left and right to see if you missed any fork in the tunnel. More to come later...
----------------------------------------------------------------------------------------------------------------------------------
#0: This is precisely why I think mathematicians often say "Want ____" at every next challenging step of their proof, especially since their proof structure isn't as rigorous as ours #1.
#1: Of course not to say they are incorrect, but I have a couple of guidelines I think every mathematician should follow because I see that every problem can be separated into "structural/organizational" and "creativity" steps.
The former includes things such as writing down the question in uniform symbolic notation (1) people are too proud to change, but 2) english words that technically mean the same thing evoke different meaning depending on the audience (but life never stops, so we can't ever unify anything)), forming predicates (keyword: Let) and writing down the proof structure (keywords: Assume when encountering a universal quantifier, and Choose when encountering an existential quantifier (assuming that we need to set the variable to do the proof)). I mean, this is basically what was taught in CSC165, and so any proof can be simplified greatly. Also important to note:
1) Indents are pretty (dang) useful
2) Stop interchanging "assume" with "let", "arbitrary" with "generic", "exists" with "there is" and "any" with "every".
3) There must be care and balance into choosing symbols and operators. In the subject level, fields should be consistent with their choices of symbols and operators, and as much as possible share symbols and operators with other, at the very least interacting (i.e. all...), fields. In the teaching level, breaking down ideas into variables doesn't necessarily help teach a concept. It may be more mathematically rigorous, but at the cost of intuition (that's why MIT's MCS makes more intuitive sense than our course notes).
4) Stop interchanging quantifiers and predicates. Read from left to right! (unless there is much more payoff for intuition or clarity).
5) a > x > b and a > y > b is usually better shown as a > x, y > b. (But sometimes my mind just seems to float away at this representation and I think it's two parts. I don't like assuming that students pay attention, but neither do I think much progress can be done with so many details such as a > x > b and
a > y > b.)
The latter is based on one's knowledge and experience with the mathematical field of the problem.
There exists a constant k >= 0 so that for all integers n >=2, T(n) <= knlogn.
I'm sure everyone likes having good intuition to reassure themselves that they can do a particular proof #0. Hence, I myself spend a lot of time searching for the "intuitive spark" for every interesting proof I encounter. Oftentimes you'd have to skip to "mathematical manipulation" part of the proof and see where you get stuck or what is obviously needed for the next step - then you can say: "Ah, so now that I know every part that is needed, I can see that we should choose ____ at the beginning" (i.e. now I have as much as I possibly get for an intuitive sense of the proof at this point in the mathematical evaluation/manipulation of the predicate).
So I searched for intuition here.
Basically, we have to apply Thm 3.5: "If n is a power of 2, T(n) = cn + dnlogn" to T(n), since it's the only thing we know about T(n)'s value in closed form.
Thm 3.5 requires that n is a power of 2, so let's make another variable n_bar in terms of n so that we can decompose T(n) to T(n_bar).
But we want the decomposition to have T(n) <= T(n_bar), since our mindset is on the less than or equal to direction. This means we want n <= n_bar. Hopefully, creativity will conjure up
n_bar = 2^ceiling(logn), based on the facts "power of 2" and "n <= n_bar".
(If we are able to think far enough (and withstand time pressure), we can think of the proof's mathematical manipulation that follows:)
Then (Assuming that we proved T(n) is nondecreasing), we can sub in n for n_bar after transforming T(n) into Thm 3.5's expression.
Lastly, remember to show that k > 0 by referencing c >=0 and d >=0.
Proof of a bound for recursive binary search
- Let's say we try to prove for all positive natural numbers n, there exists a c in the positive real numbers, such that T(n) >= clog(n) by complete induction.
- Then in the case that n > 1, we must choose a different c' in terms of c in clog(ceiling(n/2)), this from using the induction hypothesis on T(ceiling(n/2)). Both in class and in tutorial was this step skipped. Luckily (more likely than not they did know it), it was still correct to choose "c = 1", when:
1) it should be "Then there exists a positive real number c' such that T(n) >= c'log(n)."
and 2) "# Choose c' <= 1 if c > 1, and c' = c otherwise", which technically is c' <= 1, but more with more rigour and clarity (at least it is the least level of rigour to prove something to me).
Proof of a bound for MergeSort
- Proving a stronger claim shouldn't ever be something to "pull out of a hat". I hate pulling out of a hat, because it a sad beauty to withhold when you don't know how it works. Honestly, it is intuition that allows you to choose T(n) <= clog(n - 1) from T(n) <= clog(n) because you tried the latter and saw that subtracting 1 from n may actually help. It's akin to walking through a series of tunnels to reach the other side. When you find yourself in a dead end, you don't just turn 180 degrees and walk blindly back to the entrance; instead, while walking back you look left and right to see if you missed any fork in the tunnel. More to come later...
----------------------------------------------------------------------------------------------------------------------------------
#0: This is precisely why I think mathematicians often say "Want ____" at every next challenging step of their proof, especially since their proof structure isn't as rigorous as ours #1.
#1: Of course not to say they are incorrect, but I have a couple of guidelines I think every mathematician should follow because I see that every problem can be separated into "structural/organizational" and "creativity" steps.
The former includes things such as writing down the question in uniform symbolic notation (1) people are too proud to change, but 2) english words that technically mean the same thing evoke different meaning depending on the audience (but life never stops, so we can't ever unify anything)), forming predicates (keyword: Let) and writing down the proof structure (keywords: Assume when encountering a universal quantifier, and Choose when encountering an existential quantifier (assuming that we need to set the variable to do the proof)). I mean, this is basically what was taught in CSC165, and so any proof can be simplified greatly. Also important to note:
1) Indents are pretty (dang) useful
2) Stop interchanging "assume" with "let", "arbitrary" with "generic", "exists" with "there is" and "any" with "every".
3) There must be care and balance into choosing symbols and operators. In the subject level, fields should be consistent with their choices of symbols and operators, and as much as possible share symbols and operators with other, at the very least interacting (i.e. all...), fields. In the teaching level, breaking down ideas into variables doesn't necessarily help teach a concept. It may be more mathematically rigorous, but at the cost of intuition (that's why MIT's MCS makes more intuitive sense than our course notes).
4) Stop interchanging quantifiers and predicates. Read from left to right! (unless there is much more payoff for intuition or clarity).
5) a > x > b and a > y > b is usually better shown as a > x, y > b. (But sometimes my mind just seems to float away at this representation and I think it's two parts. I don't like assuming that students pay attention, but neither do I think much progress can be done with so many details such as a > x > b and
a > y > b.)
The latter is based on one's knowledge and experience with the mathematical field of the problem.
No comments:
Post a Comment