We were debating really loudly on how to answer question 6 and in the end they picked a sample number representative of real numbers, like 2, to prove that all elements of a set of real numbers have that property that they proved o_O. Usually when you prove a statement that says "for all x in set S", you usually prove it by using and manipulating variables representative of the elements of the set rather than picking actual values right? Because there is a possibility that the number you chose just happens to have with a unique weird property that may not be a good representation of all other elements in that set..
Aaaaaaaaaand I just read the sample solution to question number 6... Exactly what I thought..
I WAS RIGHT AJKSDHFDJKFHJKASDHFJKASDHJFKHADSJCNJKSDBNCJKNXZMVNCZXMNVJCMKSNZVJKNDFVJKFASNVJNADKVNJWDKNVJNASFVKBNFJV JKASDNVJDVJADIVJBIKDFVBHFBHVBDHDBVHBDHVBHDBVBHDSbvHBDSZBCXHBHCBXDHVBHCHDBHCBHBVBdhVBDHbVHDBHVBHDBVHCBJDSbHDBSHBDSJVCHSDBVHSDVJDS
*flips table
ARGHHHHHHHHHHHH
Uhh... so yah complexity of a program...
What is a Loop Guard(LG) in a program? (Refer to Friday, March 8th lecture)
When writing an equation like 4n^3 + 3n^2 + 2n + C, where C is a constant,
How do you "overestimate" to rewrite this expression in Big-O Notation?
I know you take the term with the greatest degree, but in the last slide of Friday's lecture, why is the coefficient of this term the sum of the coefficients of the other terms? I believe it resulted in O(n^3), I'm not entirely sure, the slides are not exactly up yet..
For universal quantifier NEVER pick explicit values, just because it works (or doesn't work) for the value you picked tells you nothing about whether or not it's true for other values, so you certainly can't say that it is true for ALL values by checking certain specific values.
ReplyDeleteI can't answer your question about the Loop Guard since the slides for March 8 aren't up yet so I can't see what Prof. Heap covered that lecture.
As for the the overestimating, given the function 4n^3 + 3n^2 + 2n + C, the function 4n^3 + 3n^3 + 2n^3 + Cn^3 (same function, but notice all n's are cubed) is definitely equal than or bigger than it right (for n >= 0)? And of course 4n^3 + 3n^3 + 2n^3 + Cn^3 = (9 + C)n^3, which is where the sum of the coefficients come from.
Simlarly, say you have 3n^2 - 6n + 4, this can be overestimated by 3n^2 + 4n^2 = 7n^2. Notice the "- 6n" disappeared, because removing any negative terms will obviously increase the total value.
Ah so it's all in the >= sign
ReplyDeleteAnd for the: 3n^2 - 6n + 4 we ALWAYS remove negative terms because we're trying to simplify the expression that gives the maximum value in a comparison with a >= operator?
Oh and the lecture slides for Mar 8 are up
Thanks for the help!