Week 8: big-Oh and Worst Case

This week, I learnt how to figure out the maximum steps which require for the while loop to be completely executed. Danny used both upper and lower bound to figure out how many steps the function had taken. Moreover, Danny presented the class a definition of big-oh and how to prove the big-Oh of n^2. At first, I was relieved to see the while loop. Since I had so many practices regarding while loop for my python class. But again, to find the step the function had taken and to find the relationship between the number of step the function had executed and the unknown variable was quite a tough work. Anyway the main topic which the class covered was big-Oh(n^2). The definition was like this:

- count the number of steps to show the function executed in order.
- it has be a set of function which does not go faster than n^2 to satisfy the condition.
- the highest order is the top-priority in regards to the big-Oh problem.

The symbol for big-Oh is O. #note somehow Danny used a symbol which is clearly different to mine for big-Oh, but I found that the symbol of big-Oh is the same, it was just a problem with what kind of font style was used.

One thing I got reminded during this week is how while loop can lead to execute infinite steps, if the programmer does not make the while loop function properly. Once again, Danny also reminded the class when analyzing the while loop, you first need to realize this code actually works properly.

And then there was an assignment 2 for CSC165 I had to complete this week which became a good review for my upcoming term-test 2. What really caught my attention this week was use of floor function in the proof. I tried the proof of floor function and kept trying to prove other delta-epsilon limit question besides the questions on assignment 2 to ensure I know what I am doing this week.

In conclusion, in this week,  I am actually glad that I visited Danny's office to see what the questions on assignment 2 actually meant, this way, I can also review for my test better without a misunderstanding.

Oh and one last thing, Trick or Treat! #It is just my Halloween mood...

Week 7: Sorting algorithm complexity

This week, I learnt how to sort algorithm complexity. Moreover I learnt how to prove and disprove the claim. To prove falsity one must be able to find a negation case. Danny also told us during his lecture about the allowed interference. There are 5 inference type in the proof structure Danny introduced to us at first.

1. Conjunction elimination
2. Existential instantiation
3. Disjunction elimination
4. Implication elimination
5. Universal elimination

All above 5 allowed inferences are basically what I have learnt last week when I learnt how to prove the claim through use of proof structure. Nevertheless, thing I found easy was an implication introduction. Unlike an elimination, introduction comes up with an assumption, and based on the assumption introduced, one is able to draw out the conclusion whether the claim is true or false.

The most difficult thing that I have learnt during week 7 is about sorting algorithms. Danny introduced this topic using the card game to enable students to see how algorithms work. Somehow I felt this is a lot like what I learnt in CSC108, when I studied the looping function and its indentation on python programming. However, since I am still on a stage where I am learning Python language, this algorithms which Danny told the class is still unfamiliar to me. I guess that means I need more practice for both CSC108 and CSC165 class.

POLYA's METHOD: Now it is time for challenging question which I made for myself. This time, I followed Polya's method which  Danny instructed the class to do.

First, here is the problem. Write out the proof of the below claim,
                                 ∀x ∈ N, (∃y∈ N, x²  = 2y + 1) → (∃y∈ N, x^6  = 2y +1)
1. Understanding the problem
       The problem is asking to prove for all x which is natural number, if there is some x^2 = 3y=1, then there is also x^6 which is equivalent to 2y+1. 

2. Devising a Plan
       My plan to this problem is to figure out what value I need to substitute for y in order to satisfy the claim. Also I need to keep in mind about the power rule as I need to use this rule to figure out x^6 in terms of x^2. Also what I already know is that there is domain assumption for all x which is natural number. Also ∃y∈ N on the left hand side is included in antecedent which means this ∃y∈ N is also a part of antecedent assumption. Also I need to specify two y values; one for antecedent and the other for consequent by using the symbol y' and yo. 

3. Carrying out the Plan
∀x ∈ N, (∃y∈ N, x²  = 2y + 1) → (∃y∈ N, x^6  = 2y +1)
    Assume x ∈ N      # Domain assumption
         Assume ∃y∈ N, x²  = 2y + 1      # Antecedent assumption
               Let yo be such that x = 2yo +1
                     Let y' = 4yo³ + 6yo² + yo              # since yo ∈ N
                     Then, y' ∈ N.
               Then, x^6 = (x²)^3 = (2yo + 1)³ = 2(4yo³ + 6yo² + yo) +1 = 2y' + 1
               Then, ∃y∈ N, x^6  = 2y +1
          Then, (∃y∈ N, x²  = 2y + 1) → (∃y∈ N, x^6  = 2y +1)           # introduce∃
     Then, ∀x ∈ N, (∃y∈ N, x²  = 2y + 1) → (∃y∈ N, x^6  = 2y +1)        # introduce ∀

4. Looking back 
       Looking back this problem, I think it is possible for this claim to true, as I was able to prove this claim using what I have learnt so far from week 1 to 7. I just add few comments on the proof outline just to make sure I did not mess anything up. Also I checked using yo = 1 and y' = 11 to see whether my proof to this question is actually correct. 

Week 6: Multiple Quantifier, Proof, Limit

This week, although there were only 2 lectures in a week, most of the materials we covered was about how to prove something false through the proof structure that I have learnt in week 5. In order to disprove a sequence, Danny told the class that we need to use the negation and find a counter example by assigning the value to each variable which still satisfies the domain assumption and antecedent assumption. The most difficult thing I have found during this week was proof about limits. In Danny's lecture slide, "proof about limits", Danny told us that sometimes in a claim, there are some variables which you cannot control its value. In this case, you need to find what variable you might want to change to make the claim true. Sadly during this week, I had another mid-term test in other course and 1 more mid-term test remaining next week, so I did not really have a time to review my lecture note. As I spent my time studying for my exam on Thanksgiving day, I believe that this week's Thanksgiving day may be the most productive Thanksgiving day I have ever had.

Week 5: Contradiction, Existence, Sequence

This week, I had learn how to prove the statement's existence. During the last week, I worked on how the proof structure outline works. Although it was no easy job memorizing all the step and justification to clarify what happens to each step, it still was interesting how using what I have learned up till now to prove something. Of course, what really motivated me to learn the proof structure even more than any of the week was the term test 1 which took a place on Wednesday. However, I have been kept track of my Slog to review the course materials and come up with some question (mathematical approach) to enhance my knowledge on mathematical reasoning, so somehow I was well prepared for the test.

During week 5, for most of time I have spent my time studying proof, contradiction, and symbolic logic. What I really found difficult during week was the translation of natural language into symbolic logic especially, when I didn't know whether to use a conjunction or an implication. Here is some mathematical approach I came up for this week. 

Let D be the set of all car and people. 
Let P be the set of people.
Let C be the set of Car.
Let B(x,y) interpret as "x bought y".
And let L(x,y) interpret as "x likes y". 

Now using these symbolic logic, I will create a sentence in natural language and translate back into symbolic logic using the condition and definition of each symbol that I have listed above. Now here is the sentence which I have created.

There is a person who didn't  like any of car he/she bought. 

Now to translate the above sentence into the symbolic logic, I need to think about is there needs of implication or conjunction. As I carefully examine the sentence I created, I realized what because of using word "who", that I might need both conjunction and implication to construct a symbolic logic which contains the same meaning. 

                             ∃x∈ D, P(x) ∧ ∀y∈ D, (C(y) ∧ B(x,y)) →  ¬L(x,y) 

The reason why "not like" should go after the implication sign is that the example sentence which I constructed can be interpreted as "All the car a person bought, he didn't like it." Thus, using both concept of conjunction and implication I translated the natural language into symbolic logic.  

Although this week was about how to write a proof, since the class did not learn much information about this due to term test 1, I decide to write something which I had a trouble on during my study for the term test 1. As my reflection on term test 1, I think it went pretty well compare to other questions which I solved for the practice. 

Week 4: Implication/Disjunction, Mixed Quantifiers, Proof

This week, I learnt further information regarding implication and disjunction. In addition to that, I got to realize how the sentence structure can affect the meaning which the text delivers to the readers. For instance, in Danny's PowerPoint slide, "for all, one...one for all", Danny told the class that the def for all_exist (X, Y) can only be true and not the other way around in some case, meaning the converse of the implication can be false depending on how the claim is arranged.

Let's use these two claims which will be different from Danny's example to improve my understanding on the difference in the arrangement of "for all" and "exists". This will be my mathematical approach to review my material for this week. 

∀x∈ X, ∃y∈ Y, x/y = 2

∃y∈ Y, ∀x∈ X , x/y = 2

X = Y = {2, 4, 8, 15}

The first claim can be interpret as "For all x, there exists y which can be used to make x divided by y to obtain 2. 

Now the when we look at the second claim, this can be interpreted as "There is y, which for all x can be used to obtain x divided by y equals to 2."

The first claim is the only right case, since you can choose one element of x and one element of y's result can lead to x/y = 2. Whereas  the second claim gives the condition which when you choose one element in set X, all element in set Y should bring the result of x divided by y equals to 2. Thus, depending on how you arrange universal and existential claim, the sentence or the equation may or may not make a sense. 

One thing I found difficult during this week was double quantifiers. Danny told us that there are three ways in which you can show that subset of Cartesian product N x N (Here, the letter N represents Natural number and this is one of example Danny went through) is non-empty. At first, I had no idea what Danny was talking about in his slide "double Quantifier". However, soon I realized that when there are two same types of claim such as two existential claims, the order of the claim does not affect the information deliver to the audience. Then later, Danny answered that unlike the "for all" and "exists" problem which I wrote out above, within the double quantifiers, the arrangement does not affect the logic. 

As my reflection, I feel like the course material is getting complicated as the time passes by. That is why I think keep reviewing the materials that I learnt in the class every day to prepare myself to face even more complicated logic problem. This week, I have been really busy with my assignment 1 which had become a good exercise for me to review the course materials from week 1 to week 3.