Final Week: Exam Prep

This week, I am reviewing for my upcoming final exam. I am going over my notes and practice questions that are posted on the website. Moreover, I put some comments and I found some websites really interesting, so I will post those other student's blog which I commented and think did an outstanding work on their slog. Here are few slog link which I want to recommend to other students who are having a difficulty of writing their entry for students who go to the university next year.

 Some recommended SLOGs(which I commented):

http://thesnailslog.blogspot.ca/

http://juliansongslog.blogspot.ca/

http://kaileyhe.blogspot.ca/

http://celinasopiniononcsc165.blogspot.ca/

http://csc165weeklyslog.blogspot.ca/

The below link showed a good approach to how to do problem solving episode.

http://itssoclogged.blogspot.ca/

The below link showed an extraordinary way to show his or her understanding on the halting problem which I had experienced a difficulty. 

http://livinthesloglife.blogspot.ca/2014/11/halting-problem-visualized.html

After going through many other student's SLOG, I found some SLOG are worth commenting and very interesting to review. Now it is time for me to go back to study. 

Thank you!

Week 12: Computability & Review

This week, in the lectures, Danny taught the class about the computability, and how we need to use a proof by contradiction to prove some claim to be non-computable. Moreover, I learnt how countable which I learnt in week 11 can be listable by seeing the example given by Danny. Although this concept especially the diagonalization, was hard for me at first, but with a help of professor, I was able to overcome its difficulty. Also during this week, I spent my time to finish off the assignment 3. Despite of some technical issues on CDF, I was able to ask questions that confused me on piazza to get the answer that I want. The most difficult thing I found this week was not in the lectures. It was in the review section that the class had. I guess I better study and review all the course materials I have learnt so far.

Oh, and this week's tutorial was the last tutorial I had for my CSC165 class. Although it was for a short time, I thought tutorial was really worth in terms of letting the students to review the class materials for the quiz. I also want to thank my TA for a great help on the concept of the big-Oh and omega proof. Time sure flies fast, and it is surprising for me to find out it is almost time for the final exam....

What I will do for the remaining this week is to study and go over the lecture slide from week 1 to 12.

Week 11: Halting Problem & Computability

This week, there was a reading week thus the class only had two lectures this week. During this week, Danny taught the class about the halting problem and comparability. Most of time, he used the python program which most of us were familiar of. Danny first introduced the algorithms which we are able to solve without a problem. However, Danny explained the class that not all the algorithms can be explained and solved by showing the example as below.

def collatz(n) :
    while n  >  1 :
       if  n  >  1 :
           n = n / 2
       else:
           n = 3*n + 1
    return "Reached 1..."

No matter what natural number n, you put for the above function collatz, the code will execute infinitely, without any halt. This example is what caught my attention as I tried to find the natural number which allow the function to halt, I was able to see how the coding in the computer program can be interesting.

Next, Danny taught the class some terminology we had to be familiar of such as computable and non-computable. Halt function is the one of examples for non-computable function.

Moreover, by relating to the topic of computable, Danny introduced how the implication works when the terminology "computable" is involved. For instance, "if g is computable, then f is computable", its contrapositive which is "if f is not computable, then g is not computable" should be true as well.

What I found really difficult this week was the topic of diagonalization and the definition of the terminology, "countable" and "non-countable".  Countable indicates when lAl < lNl, A is countable. For instance, the rational numbers can be consider as countable.

Thus this is just brief summary of what I learnt so far this week. By the way, there was no quiz this week, so I felt somewhat disappointing as I was not able to get the practice handout regarding the previous week's course materials. The weather is starting to get cold, but my passion towards the code will never fade away.

Week 10: Big-Omega & General Properties

During this week, I learnt about the big-omega which is almost opposite to big-Oh. Although when I express f ∈ Ω(g), this indicates ∃c∈ R+, ∃B∈ N, ∀n ∈ N, n > B → f(n) > cg(n). Whereas f ∈ O(g) indicates ∃c∈ R+, ∃B∈ N, ∀n ∈ N, n > B → f(n) < cg(n). Moreover I learnt about how I can prove even if the statement involves both big-omega and big-Oh. What I found difficult during this week is that when there is big-Omega or big-Oh in the antecedent for the complex statement, I had to assume the antecedent but at the same time, I need to represent the big-Oh or big-Omega in the antecedent using two variables, c, and B. What I found easy during this week is that the concept of big-Omega is very similar to the concept of the big-Oh which I have review last week. This week's tutorial went fine and through continuous tutorials, I feel like I am understanding more and more about logical proof for mathematical reasoning. As usual, I did few reviews on this week's material and did few practice problems which is on CSC165 Website to improve my knowledge. 

Overall, in this week, my condition is good compare to other weeks. However, tomorrow, Danny told the class that he is going to post the assignment 3. So I guess I will use my time efficiently during my reading week by doing the assignment 3. Doing assignment 3 will be a good practice before the final exam.    

Week 9: big-Oh of Polynomials, non-polynomials & Problem-Solving Episode

This week, I learnt how to solve the problem involving big-Oh with polynomials. Later on this entry, I will show the second question approaches using Polya's method. (note: my first problem solving using Polya's method was in week 7 entry, but soon I realized that instead of solving just the claim, I had to use the problem solving episode, so I am making another problem solving episode using the Polya's method.) The main thing I learnt this week was how to prove big-Oh when the claim is in polynomials. Sadly, with term test #2 and technical issues on Friday, the class was not able to properly cover the part of big-Oh with limits.

Anyway, what I really found challenging this week was when polynomial consists of subtraction and maximum slicing, I had to think really hard to prove that it is part of big-Oh. Moreover, in this week, I had to finish my assignment 2, so I was worried that I wouldn't be able to review this week's course materials. Thankfully, with enough practices and reviews, I was able to understand this week's materials as well.

In addition to that, for big-Oh polynomial cases, I had to understand how I can reinterpret the meaning and thus find a constant C, to prove the special cases.

PROBLEM SOLVING EPISODE USING POLYA'S METHOD

Now here is the problem solving episode approach using Polya's method. My problem solving episode will be on Paper folding which I did in week 3 with Danny Heap. Problem was as follows in the below:

You are given one strip of paper with each hand held by your hand. Then you would need to do fold such that fold would be folded from left to right. (p.s. I was trying to upload the video to explain this more accurately, but my video quality was so bad due to the darkness, so I will just explain it in a word.) For instance, you need to fold the strip of paper so that the left end of the strip is now on top of the right end of strip of the paper. By repeating this steps several times, you need to be able to predict the sequence of ups and downs for any number of fold you did on the strip of the paper. Also I add an additional question that what is the sequence pattern when you did 6 folds without actually folding the strip of paper?

1. Understanding the Problem
First, I know that as I fold my strip of paper as instructed, then the number of ups and downs will rise. Condition given in this problem solving episode is when one fold n times, how will the sequence pattern  of ups and downs be represented. Data was obtained through the experiment. My group and I followed the instruction and did a folding from 0 to 4, and here is sequence pattern we got for each folding time. Also note that d represents down creases, u represent up crease, and n represents number which is natural number. Also I need to find the sequence pattern when I did 6 folds without actually folding the strip of paper.

when 0 fold: no up and down can be observed.
when 1 fold:   d
when 2 folds: ddu
when 3 folds: ddudduu
when 4 folds: ddudduuddduuduu


2. Devising the Plan
Looking at the data my group obtained, we found the connection that as long as the number of fold is greater than or equal to 1, as when n increases by 1, the number of down appeared on the strip of paper increased twice. Mathematically number of d is 2^(n-1), except when number of fold is 0. As for number of up, the number of up appeared on the paper can be represented as (number of d -1). Now, I will represent this using the table 1.

Table 1

Number of fold	Sequence Pattern	Number of u	Number of d
0	none	0	0
1	d	0	1
2	ddu	1	2
3	ddudduu	3	4
4	ddudduuddduuduu	7	8

Soon our group realized there was another relationship between number of fold and the sequence pattern using the idea of the symmetry. So I am going to rewrite my sequence pattern using the table 2.

Note d: first symmetry, d or u: second symmetry, d or u: third symmetry,  d or u: fourth symmetry

 Table 2

Number of fold	Pattern	Number of different Colour Symmetry
0	No pattern observed	0
1	d	1
2	d      d      u	2
3	d  d  u  d  d  u  u	3
4	ddudduuddduuduu	4

                                                  
  (p.s. please the pattern you might see on the blog may be not organized. I am deeply sorry for the inconvenience)                                                                            

Judging from the table 2 above, I was able to find out that for n folds, there are n different numbers of symmetry which can be observed on the sequence pattern. Moreover, as the number of n increases by 1, on the left side of (n-1)th symmetry, there is addition of d, and on the right side of (n-1)th symmetry, there is an addition of u. For instance, when n = 3, on the second symmetry I need to add d on the left of d and u, then add u on the right side of  d and u.
Also I found that the very first symmetry can only be d.


3. Carrying out the Plan
Using what I know from section 2.Devising the plan, now I will be able to find the sequence pattern when  number of fold(n) is 6. First I know that there will be 6 different colour symmetry. Also I know that there are 32 d in the sequence pattern through use of 2^(n-1) = 2^(6-1) = 2^5 = 32. As for the number of u appeared on the sequence will be then 32 -1 = 31. Also from section 2, I know that there is one more d from the fact that there is only one d observed when there is 1 fold on the strip of the paper.

note that d or u: fifth symmetry, d or u: sixth symmetry

Thus, when you did 6 folds, the sequence of pattern is as below:                                  ddudduuddduuduudddudduuudduuduudddudduuddduuduuuddudduuudduuduu  

Also when you did n folds:
-you need to add d on the left side of (n-1)th symmetry from the previous pattern observe which is when there is n-1 folds.
-you need to add u on the right side of (n-1)th symmetry from the previous pattern observe which is when there is n-1 folds.

4. Looking back
To check whether the sequence pattern when n=6 is correct, I redid the problem and also counted the number of u and d to ensure that when there is 6 folds, there are 31 u and 32 d appear in the sequence. I can also use my solution to the n folds on the strip of paper to find the other sequence pattern such as when n=7,8,9...etc. Finally the solution to this problem can be easily find when you arrange the sequence pattern you observed in the middle, and carefully examine one by one to find its relationship. I also believe that this problem solving episode through Polya's method enhanced me how to approach to different mathematical problems.

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.