Week 8- Definition of O and Ω, and Sorting Algorithms

This lecture we started with O and Ω.

A function that grows no faster than O(n) is in the set. For example, O(n^2) means that the function grows no faster than n^2. The more formal definition for O(n^2) is that beyond a breakpoint B, f(n) is upper bounded by cn^2, where c is a constant multiplier. We can use this as an analogy for defining O(n^3), etc.. We can prove a function is in a certain O by using its formal definition, and wisely choosing a B and c.

On the other spectrum is Ω(n). This set contains all the functions that grow no slower than n. For example, Ω(n^2) contains all the functions that grow no slower than n^2: n^2, n^3, etc..

When a function is both Ω(n) and O(n), then that function is Θ(n), meaning it belongs is n.

Growth rate rankings: 1, logn, radn, n, nlogn, n^2, n^3...2^n, n^n



For the algorithm analysis part of the lecture, we learned to calculate the steps required for insertion sort and max slice. 

Insertion sort: we take the worst case possible scenario to count the steps required. For example, there is 3i + 5 steps required in a loop inside a loop. The outer loop requires n-1 iterations, so we end up with sum from 1 to n-1 of 3i+5. We simplify it, and then we can compare it with O(n^2) or Ω(n^2) with its proper definition and finding B and c.

In max slice, we only calculated the upper and lower bounds. For upper bound, we can over-estimate the number of steps; for lower bound, we can underestimate the number of steps. The trivial margin of error does not affect the answer.

 

Week 7: End of Proofs + Algorithms

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.

Week 6- Further Proofs

Furthering our discussion on proofs, we learned some more structures for proofs this lecture- more complex ones, involving more thinking.

First of all, we focused on non-boolean functions. Quantifiers cannot be applied on functions, so in order to prove a function we need to be creative. Using the definition of the functions, we can define many inequalities and comparisons that we may find useful when proving a statement. The takeaway is to manipulate expressions into forms closer to those in the definition.

Next, we learned to disprove statement by finding one counter-example- similar to what we have done before. We negate  the statement, then draw examples to find a counter-example.

Lastly, we tackled limits. This is a tricky one as this involves thinking backwards to find a proof. The example in class was tough to understand, but once I read it over again the method for finding a correct delta- the hard part is finding the start point.

Week 5: Further Proofs

This week's lecture included our midterm. After the midterm, we learned some additional methods of proving.

Last week, we learned how to prove a universally quantified implication- it was simple and straightforward. This week, the first thing we learned was using contrapositive to prove an implication. For example, to prove P implies Q, we can prove not Q implies not P; it achieves the same result. We use this when the reverse direction is easier to prove than the original.

Next up, we learned the usage of contradiction- a special case of contrapositive. This is a tricky one, and it involves assuming not Q instead of Q. Using this method, we assume P implies not Q, and look for a contradiction and disproving it.

For proof of an existential, we just need to find one example that satisfies.

The overall summary of the lecture is that one proof may consist of many different structures, and that with multiple quantifiers, zoom into smaller parts of the statement.

Week 4: Bi-Implications, Transitivity, Mix Quantifiers and Proofs

The past week, we continued learning the language of math.

First part of lecture, we mainly focused on the manipulating implications into something else, turning them into disjunctions or conjunctions, according to the question. Using distributive and identity properties, we can translate one statement into another form. Along with this, we also studied the negations of the bi-implications.

Next, in transitivity, we learned that if P implies Q, and Q implies R, then P implies R. The Venn diagram consists of P a subset of Q, and Q and subset of R.

For mixed quantifiers, the professor mentioned the differences in meaning (often complete opposites) if 2 of the universal or quantitative statement are ordered incorrectly. For example: for all x in X, there is some y in Y so that P(x,y) will mean something completely different if written: for a y in Y, all x in X, that P(x,y).

This brought us to the end of the language of math- we learned all the logical notations in this course including:
-quantifiers, statements, predicates
-implications, equivalence
-conjunctions, disjunctions, negation
-Venn diagrams, truth tables
-manipulating laws

With these topics covered, we can comfortably express many things using only symbols instead of words.

The next big topic we covered is Proofs. In order to prove something, we must find a proof and write it up. We need to structure our proof accordingly as well. For a direct proof of a universally quantified implication, we need to find a "chain" from the first expression to its implication. The structure for so is:

Proof for for all x in X, P implies Q:
Assume x in X
    Assume P(x)
       Then R1(x)
       Then R2(x)
        ...
        Then Q(x)
    Then P implies Q
Then for all x in X, P implies Q