Currently, there are four things I want to make clear in this topic.
1) The Piazza question regarding the proof of Lemma 3.6 still gets me confused, and I want to clarify this during OH.
2) Again lemma 3.6 (and this means proofs to show T(n) is non-decreasing). The proof denotes n by k instead. The third case tries to show that for k > 2, P(1), P(2), ..., P(k-1) implies P(k). I tried the proof itself several times and I still don't agree that "Since P(k-1) holds, to prove that P(k) holds as well, it suffices to prove that T(k-1) <= T(k)." I suppose that (if an error were to exist, it would have to be here) the proof goes on to show that since P(k-1) holds: "for every positive integer m, if m < k - 1, then T(m) <= T(k-1)", then T(m) <= T(k-1) <= T(k), the last inequality needed because we are trying to show P(k), which says: "for every positive integer m, if m < k, then T(m) <= T(k)", not merely T(k - 1). Of course this would seem silly because T(k-1) <= T(k) relies on that which we are trying to prove, that: T(k) is non-decreasing.
3) Danny skimmed over an intuition by using summation(a/(b^d)) to understand the master theorem. I read the hefty (I imagine, part-proof) of the theorem in the course notes (At least I think it was here), but I couldn't see a clear connection.
4) In class, we moved on to apply the Master Theorem to more interesting examples, in particular for multiplying n-bit numbers Gauss-wise (of which I now understand after some review) and closest point pairs (of which I don't understand completely. The slides are not posted, yet - but once they are I plan to go over them with scrutiny.)
Meanwhile, I'm hoping that more examples come up on the Master Theorem, because I'm not entirely confident on the choice of a: "The number of pieces for subproblems/the number of recursive calls." It seems that only experience can aid me in understanding this.
EDIT: Most excellent! In regards to the above:
1) I see that by the definition of non-decreasing, m < n implies T(m) < T(n), but this is equivalent to m <= n implies T(m) <= T(n). This is because if m = n, then obviously T(m) = T(n).
2) If you look at the final sentence above, I think that we are making a logical loop by needing T(k-1) <= T(k), but now I understand that this is exactly what the Vassos was trying to prove. Proving T(k-1) <= T(k) is two-fold, because for one, we break out of the logical loop and two, we are able to cover the "final case" which I was so caught up on (Since we are trying to show P(k - 1), but needing to prove T(k - 1) <= T(k) as well, since P(k - 1) cover all cases (induction hypothesis cases) before that).
Sunday, 28 October 2012
Sunday, 21 October 2012
Time Complexity 2
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.
Friday, 12 October 2012
Time Complexity
Today's class was certainly my favorite hour of compsci, and I'm starting to appreciate how well Danny teaches #-1. We searched for and proved a bound on Recursive Binary Search, and I learned to appreciate - in awe - of how it all worked out. It was the intersection of intuition (trying to feel for a bound, which is like a guessing game), functional analysis (forming T(n), the time complexity for an array of size n), and proofs (which always ended up fitting in proving the function T(n) like a final piece in a puzzle, but over and over) - so basically the intersection of all mathematical things I like. What was amazing about the search for a bound was that much of the estimation could be proved through function generalisation, then in a (relatively #-4) deep mathematical detail.
Furthermore, we can immediately see the use of finding and proving bounds in our code. #0
In the creation of T(n): [If n = 1: 1. Otherwise: 1 + max(T(m - b + 1), T(e - m)).], just the presence of b, e, and m to try to show T(n) is bounded by log(n) seems a long stretch, but Danny showed us that the steps involved were:
- Examination of the recursive function: n = e - b + 1 (acc to the inputs of recBinSearch(x, A, b, e)) versus m - b + 1 and e - m, i.e. examination of the call of recBinSearch with its original inputs and the call of its split lists, in order to rewrite m - b + 1 and e - m each in terms of n #1.
- Simplifying T(n) in terms of only the variable n.
- (Assuming that we prove that T is increasing and monotonic in order to simplify T(n)) Showing that if for some k in the positive integers, n = 2^k (this equation formed from our intuitive guess of the algorithm taking log n time), then we can generalise T(n) through induction as the recursive function keeps recursing. The end result is that T(n) = log(n) + 1 = approx. c*log(n) (c being a constant, which can replace + 1 since k is a positive int). #2
- Then using (complete, in this case) induction, we can show the bound holds (theta bounded, in fact) by c*log(n).
I want to master this #-6.
#0: As per usual, everywhere that is log(n) n this blog is in fact log(n)/log(2), but I strongly believe that the "2" should still be written as a subscript. It was once drilled into us that the natural numbers include 0, and that worked out well. Now that I am practicing more algorithms, I hope to get used to this mindset more often as well (TBH, it's a bit cocky for compsci to not write in these things, because they are distinct mathematical objects without writing in these details - the same goes for how there is a list of assumptions the program expects you to know beforehand #-2, but that belongs in another post #-3).
#1: This step took good thought in terms of using the floor/ceiling rules (which was so jexy), which I now remember is the the third most thing I fear, but which I also remember I started to really enjoy last semester. We'll see how things go. I need a list of the rules!
#2: I'm trying to find out what kind of math this generalisation is. Of course many fields of math are about generalisation, but where is this kind... of functional analysis (is that it)? Or convergence and limits to reach a convergence point? It is so absolutely addicting! Then there is graphical analysis to find out how the "bound" or convergence point acts compared to other functions. At least I can trust it to be in this course.
#-1: Most everyone will agree with me that at least for this class, he taught well (regardless of whether one thinks this post "sucks up", because, mind you, that will never be my intent). His analogies were absolutely spot on, and he gave them in nearly every part of proving the time complexity. We studied the same thing in CSC165 (at least I think so), but the prof didn't have much time at all to explain what we were trying to prove and how induction related to it at all. But really, the proof today was so Ihzp55Cuo7M.
#-2: I'm not talking about the math prereqs - those were useful.
#-3: I also want to post about what my syntax for a program would be, but I shouldn't be so cocky without having taken a theory course of prog languages (it's just that the previous syntax looks horrible... and takes away from clarity).
#-4: Relatively somewhat... doesn't matter, I love it. I'd post this proof on my wall if the paint didn't get stuck and if I didn't feel so much of a hipster atm.
#-5: Do you think I should have hidden in binary first? Google is too good and binary
#-6: I predict at least 40% of people will have this in their blog.
Furthermore, we can immediately see the use of finding and proving bounds in our code. #0
In the creation of T(n): [If n = 1: 1. Otherwise: 1 + max(T(m - b + 1), T(e - m)).], just the presence of b, e, and m to try to show T(n) is bounded by log(n) seems a long stretch, but Danny showed us that the steps involved were:
- Examination of the recursive function: n = e - b + 1 (acc to the inputs of recBinSearch(x, A, b, e)) versus m - b + 1 and e - m, i.e. examination of the call of recBinSearch with its original inputs and the call of its split lists, in order to rewrite m - b + 1 and e - m each in terms of n #1.
- Simplifying T(n) in terms of only the variable n.
- (Assuming that we prove that T is increasing and monotonic in order to simplify T(n)) Showing that if for some k in the positive integers, n = 2^k (this equation formed from our intuitive guess of the algorithm taking log n time), then we can generalise T(n) through induction as the recursive function keeps recursing. The end result is that T(n) = log(n) + 1 = approx. c*log(n) (c being a constant, which can replace + 1 since k is a positive int). #2
- Then using (complete, in this case) induction, we can show the bound holds (theta bounded, in fact) by c*log(n).
I want to master this #-6.
#0: As per usual, everywhere that is log(n) n this blog is in fact log(n)/log(2), but I strongly believe that the "2" should still be written as a subscript. It was once drilled into us that the natural numbers include 0, and that worked out well. Now that I am practicing more algorithms, I hope to get used to this mindset more often as well (TBH, it's a bit cocky for compsci to not write in these things, because they are distinct mathematical objects without writing in these details - the same goes for how there is a list of assumptions the program expects you to know beforehand #-2, but that belongs in another post #-3).
#1: This step took good thought in terms of using the floor/ceiling rules (which was so jexy), which I now remember is the the third most thing I fear, but which I also remember I started to really enjoy last semester. We'll see how things go. I need a list of the rules!
#2: I'm trying to find out what kind of math this generalisation is. Of course many fields of math are about generalisation, but where is this kind... of functional analysis (is that it)? Or convergence and limits to reach a convergence point? It is so absolutely addicting! Then there is graphical analysis to find out how the "bound" or convergence point acts compared to other functions. At least I can trust it to be in this course.
#-1: Most everyone will agree with me that at least for this class, he taught well (regardless of whether one thinks this post "sucks up", because, mind you, that will never be my intent). His analogies were absolutely spot on, and he gave them in nearly every part of proving the time complexity. We studied the same thing in CSC165 (at least I think so), but the prof didn't have much time at all to explain what we were trying to prove and how induction related to it at all. But really, the proof today was so Ihzp55Cuo7M.
#-2: I'm not talking about the math prereqs - those were useful.
#-3: I also want to post about what my syntax for a program would be, but I shouldn't be so cocky without having taken a theory course of prog languages (it's just that the previous syntax looks horrible... and takes away from clarity).
#-4: Relatively somewhat... doesn't matter, I love it. I'd post this proof on my wall if the paint didn't get stuck and if I didn't feel so much of a hipster atm.
#-5: Do you think I should have hidden in binary first? Google is too good and binary
#-6: I predict at least 40% of people will have this in their blog.
Sunday, 7 October 2012
Recap: Structural Induction
The proof for P(n): "sum from i = 0 to n of F(i) = F(n+2) - 1".
- At first I fell for the same trick as a previous TA of this course by thinking that the minimum base cases necessary for the proof were n = 0 and n = 1. After discussion with Danny, I realized that as attractive as this was, it was incorrect. Just because the fibonacci is defined as:
F(n) = n if n < 2 and F(n-2) + F(n-1) if n >= 2,
it does not mean that all inductive proofs on n require base cases n = 0 and n = 1. In this proof, it is completely irrelevant since the definition of F(n) is already set in stone, i.e. given. We can already use it (like in the IS), and we are not trying to prove the fib seq.
The final thing covered before today was how to translate a recursively defined sequence into closed form. I was crazy excited when Danny showed this because this was something that had crossed my mind many times before. He gave the example of how as the fib sequence grew, it increasingly became closer to a fixed ratio - through this ratio. He represented F(n) as approx. r^n, then the fibonacci sequence could be rewritten as r^n = r^n-1 + r^n-2. This could be written (oh so beautifully) as r^2 = r + 1, to find that solns phi = [1+- sqr(5)]/2. This phi is the golden ratio phi (how amazing is that!) and F(n) can be written in closed form as (phi^n - phibar^n)/sqr(5), where phi = [1 + sqr(5)]/2 and phibar = [1 - sqr(5)]/2.
- At first I fell for the same trick as a previous TA of this course by thinking that the minimum base cases necessary for the proof were n = 0 and n = 1. After discussion with Danny, I realized that as attractive as this was, it was incorrect. Just because the fibonacci is defined as:
F(n) = n if n < 2 and F(n-2) + F(n-1) if n >= 2,
it does not mean that all inductive proofs on n require base cases n = 0 and n = 1. In this proof, it is completely irrelevant since the definition of F(n) is already set in stone, i.e. given. We can already use it (like in the IS), and we are not trying to prove the fib seq.
The final thing covered before today was how to translate a recursively defined sequence into closed form. I was crazy excited when Danny showed this because this was something that had crossed my mind many times before. He gave the example of how as the fib sequence grew, it increasingly became closer to a fixed ratio - through this ratio. He represented F(n) as approx. r^n, then the fibonacci sequence could be rewritten as r^n = r^n-1 + r^n-2. This could be written (oh so beautifully) as r^2 = r + 1, to find that solns phi = [1+- sqr(5)]/2. This phi is the golden ratio phi (how amazing is that!) and F(n) can be written in closed form as (phi^n - phibar^n)/sqr(5), where phi = [1 + sqr(5)]/2 and phibar = [1 - sqr(5)]/2.
Recap: Well-ordering Principle
(#0)
The proof for 1) 0 <= r <= n and 2) q, r unique with the set R = {r in natural numbers | There exists q in natural numbers. m = qn+r} (which has a smallest element) for each m and n was very messy in my mind.
--------
Alright, I was going to write a problem-solving episode here, but I believe I understand the proof well now. Part of the confusion was the lack of emphasis on the def'n of well ordering in class, as simple as it sounds. Then there was the separation between needing to show parts 1) and 2). At the very least, now I see that:
- We can do double induction on m and n.
- Since we assumed m to be arbitrary, it helps show us that the set R is nonempty by choosing q = 0.
- Well-ordering is probably the most tricky type of induction for me. Let's try to find some patterns, as in the proof below.
The proof for all natural numbers n > 3. P(n):"Every round-robin tournament w/ n players that has a cycle has a 3-cycle" was cool (since analysing a game takes away any boredom a CS course could bring).
- This gave me intuition on how to use WOP #-1. Firstly, I learned that a set should be constructed when we are looking to prove a particular element is the smallest element of the set wrt to the claim we have to prove. Then, I also learned that the elements should be natural numbers (to show the set is a subset of the natural numbers) and that the claim can help us show the set is nonempty (since the claim asks to prove that an element of the set is the smallest one, but this assumes that the element exists in the set in the first place, which is hidden somewhere in the claim itself).
- An important thing to remind myself is that to prove the element is the smallest, we can do a proof by contradiction. We assume the smallest element is larger than that which we want to show is the smallest element, then we show how this assumption leads to a contradiction, oftentimes by being able to find a smaller element or failing to remain in an assumed domain.
- Finally, I only noticed that the two cases: p1 > p3 and p3 > p1 actually fulfills the law of the excluded middle, and can hence be used ain a proof by cases.
Just reading MIT's MCS book, their suggestion on the WOP goes along the lines of:
- Create a set C that is all the counter-examples to the claim.
- Assume the set is non-empty and that by the WOP, it has a smallest element n.
- Show that this assumption leads to a contradiction.
- Then the assumption is wrong, C is empty, and the claim holds.
In this form of a WOP proof, I noticed that one way the contradiction is found is by noticing that all elements smaller than n do have the claim hold. This is similar to the induction hypothesis holding in a complete induction proof. Then we can take the constituent parts of n and use the induction hypothesis on each of those parts to show that the claim does indeed hold for n. This contradicts the assumption that n is the smallest counterexample, because it isn't a counterexample. This is enough to show that the WOP doesn't hold, which means that the assumption is wrong, so the claim holds.
Okay, back to studying.
#-1: oppa gangnam style
The proof for 1) 0 <= r <= n and 2) q, r unique with the set R = {r in natural numbers | There exists q in natural numbers. m = qn+r} (which has a smallest element) for each m and n was very messy in my mind.
--------
Alright, I was going to write a problem-solving episode here, but I believe I understand the proof well now. Part of the confusion was the lack of emphasis on the def'n of well ordering in class, as simple as it sounds. Then there was the separation between needing to show parts 1) and 2). At the very least, now I see that:
- We can do double induction on m and n.
- Since we assumed m to be arbitrary, it helps show us that the set R is nonempty by choosing q = 0.
- Well-ordering is probably the most tricky type of induction for me. Let's try to find some patterns, as in the proof below.
The proof for all natural numbers n > 3. P(n):"Every round-robin tournament w/ n players that has a cycle has a 3-cycle" was cool (since analysing a game takes away any boredom a CS course could bring).
- This gave me intuition on how to use WOP #-1. Firstly, I learned that a set should be constructed when we are looking to prove a particular element is the smallest element of the set wrt to the claim we have to prove. Then, I also learned that the elements should be natural numbers (to show the set is a subset of the natural numbers) and that the claim can help us show the set is nonempty (since the claim asks to prove that an element of the set is the smallest one, but this assumes that the element exists in the set in the first place, which is hidden somewhere in the claim itself).
- An important thing to remind myself is that to prove the element is the smallest, we can do a proof by contradiction. We assume the smallest element is larger than that which we want to show is the smallest element, then we show how this assumption leads to a contradiction, oftentimes by being able to find a smaller element or failing to remain in an assumed domain.
- Finally, I only noticed that the two cases: p1 > p3 and p3 > p1 actually fulfills the law of the excluded middle, and can hence be used ain a proof by cases.
Just reading MIT's MCS book, their suggestion on the WOP goes along the lines of:
- Create a set C that is all the counter-examples to the claim.
- Assume the set is non-empty and that by the WOP, it has a smallest element n.
- Show that this assumption leads to a contradiction.
- Then the assumption is wrong, C is empty, and the claim holds.
In this form of a WOP proof, I noticed that one way the contradiction is found is by noticing that all elements smaller than n do have the claim hold. This is similar to the induction hypothesis holding in a complete induction proof. Then we can take the constituent parts of n and use the induction hypothesis on each of those parts to show that the claim does indeed hold for n. This contradicts the assumption that n is the smallest counterexample, because it isn't a counterexample. This is enough to show that the WOP doesn't hold, which means that the assumption is wrong, so the claim holds.
Okay, back to studying.
#0: I want to meet the prof who wrote this book since his style would be very similar to mine. Very complete but easy to fall asleep with as a result. In fact, the symbols here are so frequent that the text becomes very hard to read. Have you seen MIT's MCS book? Perfect textbook.
#-1: oppa gangnam style
Recap: Strong Induction
The proof for n>1. P(n): "n has prime factorisation" was unnecessarily (i.e. I could work on it) tough.
- Prime nums (and binary) are the two things that I struggle with the most. I'm going to look over ch1(or 0?) of the textbook for the prime factor def'n and I will work with binary more often in CSC258 (I noticed we will work with 2 complements in this class, too. It's getting better for me).
The proof for n>0 P(n): "Every full binary tree with n nodes has n odd"
- At first I didn't understand why we needed a base case, but this is a strong reminder that I can only use the IH when the IH prereqs are fulfilled.
The proof for postages (3 stamp, 5 stamp to make everything after 8)
- Once again here I practiced expressing my intuition mathematically when we separate the proof into cases of 8 <= n <= 10 and n > 10. In the second case, I followed the book, creating a variable i = n-3 to show the "loop" that can be formed with induction.
- In class Danny mentioned a MI method for the proof, but I'm thinking it is very similar.
A1Q1: (I liked my sol'n)
- Let n be the height of the ternary tree T.
- I separated the cases into when T's root had one, two, xor three children. The three children's case was analogous to the two children's case. I noted that n = 1 + max(height(left child tree), height(right child tree)). I also noted that 0<height(left child tree)<n since max(height(left child tree)<n and height(left child tree) is each at least 1 so I could do IH. Etc. This was beautiful to me.
- In a more time sensitive environment, however, I would not do a proof by cases and I would just do (assuming we got n = 1 as base case proven):
Label the children/potential children of tree T with TsubL, TsubM, TsubR.
Let Ssube = {t \in {TsubL, TsubM, TsubR}: t exists}.
Then for all (#0) s in Ssube, number of nodes of s <= 3^height(s) - 2 by IH.
Let S' = {t not in S}.
Then for all s' in S', number of nodes of s' = 0
Then the sum of nodes TsubL + sum of nodes TsubM + sum of nodes TsubR + 1 <= 3^height(T) - 2
Etc.
#0: I have come to the conclusion that using words instead of LyX commands will be much clearer... I will use them from now on.
- Prime nums (and binary) are the two things that I struggle with the most. I'm going to look over ch1(or 0?) of the textbook for the prime factor def'n and I will work with binary more often in CSC258 (I noticed we will work with 2 complements in this class, too. It's getting better for me).
The proof for n>0 P(n): "Every full binary tree with n nodes has n odd"
- At first I didn't understand why we needed a base case, but this is a strong reminder that I can only use the IH when the IH prereqs are fulfilled.
The proof for postages (3 stamp, 5 stamp to make everything after 8)
- Once again here I practiced expressing my intuition mathematically when we separate the proof into cases of 8 <= n <= 10 and n > 10. In the second case, I followed the book, creating a variable i = n-3 to show the "loop" that can be formed with induction.
- In class Danny mentioned a MI method for the proof, but I'm thinking it is very similar.
A1Q1: (I liked my sol'n)
- Let n be the height of the ternary tree T.
- I separated the cases into when T's root had one, two, xor three children. The three children's case was analogous to the two children's case. I noted that n = 1 + max(height(left child tree), height(right child tree)). I also noted that 0<height(left child tree)<n since max(height(left child tree)<n and height(left child tree) is each at least 1 so I could do IH. Etc. This was beautiful to me.
- In a more time sensitive environment, however, I would not do a proof by cases and I would just do (assuming we got n = 1 as base case proven):
Label the children/potential children of tree T with TsubL, TsubM, TsubR.
Let Ssube = {t \in {TsubL, TsubM, TsubR}: t exists}.
Then for all (#0) s in Ssube, number of nodes of s <= 3^height(s) - 2 by IH.
Let S' = {t not in S}.
Then for all s' in S', number of nodes of s' = 0
Then the sum of nodes TsubL + sum of nodes TsubM + sum of nodes TsubR + 1 <= 3^height(T) - 2
Etc.
#0: I have come to the conclusion that using words instead of LyX commands will be much clearer... I will use them from now on.
Recap: Simple Induction
(#0)
The proof for P(n): "Every set w/ n ele has 2^n subsets" was quite elegant.
- Since the end of CSC165, I have had the trouble of expressing my intuition in mathematical terms, and the bijective fn f:s^- -> s^+, f(s) = s U x (mapping from the set that doesn't include x (ele n+1) to the set that does include x (ele n+1)) was precisely (#-1) the fn needed to do so in this proof. The book itself didn't formalise the function though. I think the fn itself takes some time to create, so hopefully a more informal (i.e. ..."worded") proof of the bijection between the two sets will suffice. I practiced creating such a fn for the first assignment - hopefully it will do.
- Let S an arbitrary set with n ele. I do not know exactly how to express in mathematical symbolism: the set of subsets of S that don't contain the ele x and the set of subsets that do contain the ele x. Perhaps the former will be {/forall s /in Powerset(S): x /not/in s} and the latter will be {/forall s /in Powerset(S): x /in s}. (#-2)
The proof for P(n): "12^n -1 is a multiple of 11".
- Really a classic example of mathematical creativity. I really have to take note of this, since you can't really work forwards or backwards.
The proof for P(n): "Units digit of 4^n \in {1, 4, 6}".
- A simple proof, but when I first tackled it I couldn't express my intuition in mathematical terms.
- In tutorial, the TA expressed it as \exists z \in Z.\exists t \in {1, 4, 6}. 4^n = 10z + t (#1). I like that (#2).
Proof of A1Q4.
- I just liked the fact that we practiced claim strengthening. It really was interesting. I wonder if something will come up where we prove one strong claim version, then we need to use a variety logical rules to prove from that strong claim the weakened claim. Like if we needed to use deMorgan's and contrapositive.
Proof of A1Q3.
- So awesome. Really showed me that I need to organise (and write neatly...) when I play around with a claim.
#0: I need practice on structural induction and well-ordering. I'll look at the textbook later...
#1: Professor Ellen used '.' instead of ',' in between quantifies and predicates. I like this because many I suck at writing ',' and there are claims that involve sets of integers as this one, so '.' allows me to focus more on the claim.
#2: Dear TA, let's please proceed faster in tutorials - as much as I do enjoy how carefully you overview proofs.
#-1: Since I was brainwashed with Physics in high school, I still believe the term accurately should be used in place of precisely, as bad as it sounds. On the other hand, no one can ever know if an answer is close to "truth" or not.
#-2: This reminds me, there is so much power into solving problems by playing around with them by hand (#-3), i.e. in assignment 1 question 3, writing down the lists of 2-subsets and 3-subsets (almost like art) can really open up your mind. I have to explore this more myself.
#-3: I was going to refrain from falling into using boldface, strikethroughs, etc. since not using them really does help me gain wisdom in choosing appropriate words. More power to technology.
The proof for P(n): "12^n -1 is a multiple of 11".
- Really a classic example of mathematical creativity. I really have to take note of this, since you can't really work forwards or backwards.
The proof for P(n): "Units digit of 4^n \in {1, 4, 6}".
- A simple proof, but when I first tackled it I couldn't express my intuition in mathematical terms.
- In tutorial, the TA expressed it as \exists z \in Z.\exists t \in {1, 4, 6}. 4^n = 10z + t (#1). I like that (#2).
Proof of A1Q4.
- I just liked the fact that we practiced claim strengthening. It really was interesting. I wonder if something will come up where we prove one strong claim version, then we need to use a variety logical rules to prove from that strong claim the weakened claim. Like if we needed to use deMorgan's and contrapositive.
Proof of A1Q3.
- So awesome. Really showed me that I need to organise (and write neatly...) when I play around with a claim.
#0: I need practice on structural induction and well-ordering. I'll look at the textbook later...
#1: Professor Ellen used '.' instead of ',' in between quantifies and predicates. I like this because many I suck at writing ',' and there are claims that involve sets of integers as this one, so '.' allows me to focus more on the claim.
#2: Dear TA, let's please proceed faster in tutorials - as much as I do enjoy how carefully you overview proofs.
#-1: Since I was brainwashed with Physics in high school, I still believe the term accurately should be used in place of precisely, as bad as it sounds. On the other hand, no one can ever know if an answer is close to "truth" or not.
#-2: This reminds me, there is so much power into solving problems by playing around with them by hand (#-3), i.e. in assignment 1 question 3, writing down the lists of 2-subsets and 3-subsets (almost like art) can really open up your mind. I have to explore this more myself.
#-3: I was going to refrain from falling into using boldface, strikethroughs, etc. since not using them really does help me gain wisdom in choosing appropriate words. More power to technology.
Purpose
is the reason why everything runs. (#-1)
And one more thing - I'll be using LyX commands to express mathematical symbols when they aren't explicitly (#-4) on the keyboard. It'll make it easier to copy-paste themif when you have a similar editor.
I hope that you, dear reader, will gain some insight as I delve into my mind to try to pull out and present my thoughts on CS theory. No doubt other times I will unconsciously stray away from this - and at the very least you can learn a bit more about a random (#0 what's the difference between random and arbitrary?) person's perspective on the universal journey.
Leggo! (#-2)
And one more thing - I'll be using LyX commands to express mathematical symbols when they aren't explicitly (#-4) on the keyboard. It'll make it easier to copy-paste them
#0: In my experience, random sounds a lot more "floppy" than arbitrary. I think this is the reason why profs don't use the word random very often in proofs. An arbitrary element implies that the element has some property that the prover must take note of (like in math, it seems like we are looking in a more general sense), whereas a random element implies unexpectedness that the prover must watch out for (as in splitting the domain of the element into cases). Looking at it this way, I think the two words can be used strategically as a hint to students (/{students with specifically unique cultural norms}).
#-1: As I write this blog my hands sweat for several (I like having a mutable number just so that I don't have to re-edit) reasons: 1) first blog. 2) I have other work to do, and I'm afraid that I will get addicted to blogging, since some of my mind is already locked up in a file on my HD.
#-2: I hate short "sentences", as useful as they are (I also hate periods within parenthesis, because they are actually syntactically wrong - you are period'ing the outer sentence - so you should not period the sentence within the parenthesis, as shown). (#-3)
#-3: I like the format of my messages. I can nest them. I can use negative natural numbers for self-relecting posts and non-negative natural numbers for relevant ones. Finally, I can leave my posts as clean as proofs (sort of).
#-1: As I write this blog my hands sweat for several (I like having a mutable number just so that I don't have to re-edit) reasons: 1) first blog. 2) I have other work to do, and I'm afraid that I will get addicted to blogging, since some of my mind is already locked up in a file on my HD.
#-2: I hate short "sentences", as useful as they are (I also hate periods within parenthesis, because they are actually syntactically wrong - you are period'ing the outer sentence - so you should not period the sentence within the parenthesis, as shown). (#-3)
#-3: I like the format of my messages. I can nest them. I can use negative natural numbers for self-relecting posts and non-negative natural numbers for relevant ones. Finally, I can leave my posts as clean as proofs (sort of).
#-4: Alt keys might be something worth learning.
Subscribe to:
Posts (Atom)