The first thing we learned this lecture was proof by cases- covering all possibilities of a statement by splitting it into several cases. For example, if a question involves proving something for a natural number, we can split it into two cases: one where all are odd, another one where all are even.
We reviewed the different proof patterns: given what's known, what can we infer? There are two cases. Introduction is from a smaller statement, we can infer a larger statement. Elimination is the opposite of Introduction.
The next big topic we learned about was Algorithm Analysis. In this, we compared bubble and merge sort, and based on actual examples, determined which was faster and why. To compare algorithms, we should compare the growth factor; that is, for example, if we double the number of data to be sorted, how many times does runtime increase? Running time is the number of steps taken by the algorithm, but we only care about its growth factor.
Since n^2 is so large, n^2 + n is seen as the same thing. We only care about the highest order, because as the data set increase, n^2 will increase exponentially larger while the other terms will not increase as much.
No comments:
Post a Comment