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.
Friday, November 28, 2014
Friday, November 21, 2014
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.
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.
Friday, November 14, 2014
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.
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.
Saturday, November 8, 2014
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
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
(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.
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.
Subscribe to:
Posts (Atom)