Exams
So, Calc II. I rocked that exam, seriously. I feel like it's a high 90. I had an answer for every question, but I hesitate to say I got 100% because that's a little ridiculous and it's likely that I made a few careless errors here and there.
As for CS, I uh, did well? On CS? I didn't think it possible, but apparently it is. I estimate my mark to be somewhere between 80 and 90, but it feels more like it's between 85 and 90. There were a couple questions about Big-O notation that I wasn't sure exactly how they wanted me to do it, so I ended up doing it my own way.
One of the questions was "Prove 100(n^2 + n + 1) is O(n^2)" and I don't know the definition of Big-O in CS terms, but I do know it overall, so I just was like.. okay.. limits! So I said, "Consider (n^2 + n + 1) if lim n-> infinity ((n^2 + n + 1)/(n^2)) = 1, then (n^2 + n + 1) is O(n^2)." So yes, the limit is 1, as you can multiply it by (n^2)/(n^2) (which is just multiplying by 1, it doesn't change anything) and end up with lim n-> inf ((n^2/n^2 + n/n^2 + 1/n^2)/(n^2/n^2)) and so n/n^2 and 1/n^2 just go to 0 as n goes to infinity, and n^2/n^2 goes to 1. So it's 1/1 = 1. So n^2 + n + 1 = O(n^2). Then you go back to the fact that it's all multiplied by 100 and you say, well, 100 = O(1) because 100 is just a constant, and so 100(n^2 + n + 1) = O(1)*O(n^2) = O(n^2) QED.
The other question was prove n*sqrt(n) is not O(n) and that was done just by showing that the limit of n*sqrt(n)/n is not 1 as n approached infinity.
So the funny thing about these is that I had no idea if these answers would be acceptable since they totally don't make use of the CS definition of Big-O. Lino happened to be the one to mark this question and came up to me in the SLC shouting that he just finished marking my exam but he wasn't allowed to tell me my mark, the bastard. :P However, we had a brief "unrelated" conversation about Big-O and whether the use of limits is a valid way of going about solving certain problems, and it seems that we are in concordance.
Another kind of interesting question was the induction proof where you're told that the S_T = h_T + S_L + S_R where S_T is the sum height of the tree T, h is the height of T, and S_L is the sum height of T's left subtree L and S_R is the sum height of T's right subtree R. As in, the sum height of a tree is the sum of all the heights of all its subtrees. You're supposed to prove that S_T <= 3^h and you're given that k <= 3^(k-1).
Base case is h = 0, sum height is 0.
0 <= 3^0
0 <= 1 true.
Assume true for 0 <= n <= k where n is the height of the tree.
So for tree L of height k, the sum height is <= 3^k. Tree R of height k's sum height is also <= 3^k.
So for tree T of height k+1,
S_T <= k+1 + S_L + S_R
S_T <= k+1 + 3^k + 3^k
We're given k <= 3^(k-1) so k+1 <= 3^k
S_T <= k+1 + 3^k + 3^k <= 3^k + 3^k + 3^k
S_T <= 3*3^k
S_T <= 3^(k+1) QED.
As for CS, I uh, did well? On CS? I didn't think it possible, but apparently it is. I estimate my mark to be somewhere between 80 and 90, but it feels more like it's between 85 and 90. There were a couple questions about Big-O notation that I wasn't sure exactly how they wanted me to do it, so I ended up doing it my own way.
One of the questions was "Prove 100(n^2 + n + 1) is O(n^2)" and I don't know the definition of Big-O in CS terms, but I do know it overall, so I just was like.. okay.. limits! So I said, "Consider (n^2 + n + 1) if lim n-> infinity ((n^2 + n + 1)/(n^2)) = 1, then (n^2 + n + 1) is O(n^2)." So yes, the limit is 1, as you can multiply it by (n^2)/(n^2) (which is just multiplying by 1, it doesn't change anything) and end up with lim n-> inf ((n^2/n^2 + n/n^2 + 1/n^2)/(n^2/n^2)) and so n/n^2 and 1/n^2 just go to 0 as n goes to infinity, and n^2/n^2 goes to 1. So it's 1/1 = 1. So n^2 + n + 1 = O(n^2). Then you go back to the fact that it's all multiplied by 100 and you say, well, 100 = O(1) because 100 is just a constant, and so 100(n^2 + n + 1) = O(1)*O(n^2) = O(n^2) QED.
The other question was prove n*sqrt(n) is not O(n) and that was done just by showing that the limit of n*sqrt(n)/n is not 1 as n approached infinity.
So the funny thing about these is that I had no idea if these answers would be acceptable since they totally don't make use of the CS definition of Big-O. Lino happened to be the one to mark this question and came up to me in the SLC shouting that he just finished marking my exam but he wasn't allowed to tell me my mark, the bastard. :P However, we had a brief "unrelated" conversation about Big-O and whether the use of limits is a valid way of going about solving certain problems, and it seems that we are in concordance.
Another kind of interesting question was the induction proof where you're told that the S_T = h_T + S_L + S_R where S_T is the sum height of the tree T, h is the height of T, and S_L is the sum height of T's left subtree L and S_R is the sum height of T's right subtree R. As in, the sum height of a tree is the sum of all the heights of all its subtrees. You're supposed to prove that S_T <= 3^h and you're given that k <= 3^(k-1).
Base case is h = 0, sum height is 0.
0 <= 3^0
0 <= 1 true.
Assume true for 0 <= n <= k where n is the height of the tree.
So for tree L of height k, the sum height is <= 3^k. Tree R of height k's sum height is also <= 3^k.
So for tree T of height k+1,
S_T <= k+1 + S_L + S_R
S_T <= k+1 + 3^k + 3^k
We're given k <= 3^(k-1) so k+1 <= 3^k
S_T <= k+1 + 3^k + 3^k <= 3^k + 3^k + 3^k
S_T <= 3*3^k
S_T <= 3^(k+1) QED.