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.