This week is right before the final exam. On Monday, I handed my Assignment 3 for CSC 165. I also reviewed the past exam materials. Although I had some problems with halting function, I was able to understand the question by doing the last question on Assignment 3. Now this ends my first term at U of T. The final exam is worth 40%. So I will put my best effort into my study for CSC 165. I hope to achieve higher than 80% for the final exam. While reading other people's SLOG, I found very interesting SLOGs that I would like to share. However, it is so sad to see that some SLOG only had one or two posts for this term. I want to thank all of you.
Here are the SLOG links that were interesting to me. I also put comments on them.
http://99bugsbutaglitchaintone.blogspot.ca/
http://csc165justinsong.blogspot.ca/
http://matthewsampson165slog.blogspot.ca/
http://olivertanslog.blogspot.ca/
http://logic-station.blogspot.ca/
Again, I would like to thank professors, TAs, and my friends for their support in CSC 165. It is time to study for CSC 165 final exam! It is too bad that countability and induction won't be on the test. I want to thank all of you once again.
Tuesday, December 2, 2014
Friday, November 28, 2014
CSC 165 SLOG #11: (Week 12: Computability)
This week was the last week of CSC 165 for this semester. During the lectures, we went over computability part. One thing I learnt is Cantor's diagonalization. I also learnt that countable is listable. I also completed Assignment 3 for CSC 165. This week, CDF problem was solved and my mark for Assignment 2 came out as well on markus. Interestingly, I got the same mark as Assignment 1.
The last thing I learnt from CSC 165 lecture was induction. As I have already studied mathematical induction before, learning induction in CSC 165 was very easy.
As I finish CSC 165, I learnt various mathematical skills that are used in computer science. Unlike CSC 108 where I only learnt Python programming, CSC 165 allowed me to explore logic and mathematical proof technique which broadened my view as a computer scientist. I hope to learn more about computer science in other CSC courses. CSC 165 inspired me to pursue my career in computer science.
I want to thank Professor Heap, Larry and my TA for their efforts. Thank you very much!
The last thing I learnt from CSC 165 lecture was induction. As I have already studied mathematical induction before, learning induction in CSC 165 was very easy.
As I finish CSC 165, I learnt various mathematical skills that are used in computer science. Unlike CSC 108 where I only learnt Python programming, CSC 165 allowed me to explore logic and mathematical proof technique which broadened my view as a computer scientist. I hope to learn more about computer science in other CSC courses. CSC 165 inspired me to pursue my career in computer science.
I want to thank Professor Heap, Larry and my TA for their efforts. Thank you very much!
Friday, November 21, 2014
CSC 165 SLOG #10: (Week 11:Halting Problem and Computability)
Learning week 11 materials was very challenging for me. I had very hard time understanding the problem. I also started on my last assignment for Assignment 3 for CSC 165. I hoped that I would get the assignment on Nov 15th, so that I can finish it during the holidays. However, unfortunately, the assignment was posted this Tuesday. I hope to finish this assignment by next Wednesday if possible.
Week 11 was all about halting problem and computability. I also learnt that halt(f, n) is non-computable, but well-defined. One thing that interested me is the history of algorithm that I heard during Wednesday's lecture. Alan Turing who is often regarded as the father of computer science and algorithm developed Turing machine used in the WW2. As I was more interested in Alan Turing, I searched about him on Internet. Then, I found that Alan Turing committed suicide as he was charged as a criminal.
As a review, I also studied Larry's Week 10 slides. I learnt various terminology from Larry's slide. The slides show that Well-defined for function f is true iff we know what f(x) is for every x domain. Function f being computable means that the function is well-defined and we know how to implement function f. Others are non-computable.
I decided to practice solving the questions on the slides from last week and this week to improve my skills on proving and disproving for Big Omega and Big Theta. It's time for me to work on Assignment 3!
Friday, November 14, 2014
CSC 165 SLOG #9: (Week 10:Big Omega, Big Theta and General Properties)
This week, I learnt how to prove and disprove Big Omega, and Big Theta. I also got my second term test back. Although I wasn't able to achieve the same mark as the last time, I am very satisfied with my marks considering that this test was harder than the last one.
During the lecture, the professor went over Big Omega and Big Theta materials. The lectures were mostly focused on proving and disproving big omega and big theta. One thing I found interesting was that we have to use L'Hopital's rule in some specific cases. As I already knew what this rule is, I had no problem solving the questions. Learning how to prove 2n ∉O(n2) was very interesting as I had to apply L'Hopital's rule.
If we write this in limit, it is as shown below.
lim (x -> ∞) 2n
/ (n2)
As both numerator and denominator would become infinity, we have to do the derivation on this limit for each numerator and denominator due to L'Hopital's rule.
We get as shown below.
lim (x -> ∞) 2n ln2 * ln2 / 2
Then we can show this as shown below.
∀c∈ R+,∃nc∈ N, ∀n∈ N, n >= nc -> 2n/n2
> c
After that, we can prove this using the techniques we learnt throughout this course.
I hope to learn more in computer science mathematical expression next week to become a great computer scientist.
Saturday, November 8, 2014
CSC 165 SLOG #8: (Problem-solving Episode and Week 9 materials)
This week, I had my second term test in CSC 165 and I think I did pretty well with it. Although I had some difficulty with Question #3 of the test, I understood that question after few minutes of struggling as I already practiced prove/disprove using many practice problems, assignments and previous tests. I hope to achieve A in this test as well. Achieving great marks on both test is one of my goals in CSC 165 as these scores represent how much effort and interest I have put in CSC 165.
This week, we learnt about proving worst case and it was quite easy as it was similar to proof I have done before during the last week to prepare for the test.
Paper Folding (Problem-solving Episode)
This week, I would like to demonstrate my Polya's Method on Paper Folding problem that we did previously during the lecture. This is done to reinforce and check my understanding and approach to solve the problem.
1. Understanding the Problem
What we know is that using a paper strip, as we fold one by one, we have to find a pattern on how crease points being vertex up or down differ. I decided to label vertex up crease point as u and vertex down crease point as d. In this question, the condition is that when we fold the paper strip, one end of the strip has to meet the other end of the paper strip. If this condition is not met properly, then the result for the problem would become messed up. We have to come up with a method where we can exactly predict the fold pattern just by looking at the number of fold it has been done on the paper strip. To do that, I first thought that I could try some of the very first few folding to analyze the pattern. The unknown is the pattern that corresponds to the specific number of fold.
2. Devising a Plan
The first plan I came up with is that I try folding up to 4 times and observe whether there is any similar patterns among all these folds I have done. Next, I will record crease point vertex up and down for every folding I did. With the data collected, I will organize the data in a way that I can analyze its pattern. Then, I will try what I need to put in addition in the sequence from the first fold to the second fold. Then I will do the same thing with the second fold and the third fold and so on. Also, I will also count the number of d and u for every fold I do to analyze the pattern.
3. Carrying out the Plan
I exactly carried out the plan I devised and got the results shown below.
1st fold: d
2nd fold: d d u
3rd fold: d d u u d u u
4th fold: d d u d d u u d d d u u d u u
Just with this information that is organized like this, I was not able to find out whether these folds even have patterns or not.
I tried approaching the problem by counting the number of d and u present for each folding.
1st fold: 1d
2nd fold: 2d 1u
3rd fold: 3d 4u
4th fold: 8d 7u
However, I quickly realized that my devised plan is wrong for this part as counting the number of d and u present in the fold does not tell us anything about the patterns.
Hints for this question were given. Hint #1 was thinking recursively. Surprisingly, hint #1 was exactly what I did up until now. I approached the problem recursively. However, the problem with my approach was that I only thought that d and u would be added up to the start and end point of the folding patterns. Hint #2 was thinking symmetrically. This hint sparked my mind. With hint #2, I started to look symmetrical pattern, I immediately organized the above information like below.
Numbers 1, 2, 3, 4 represent the number of fold.
1: d
2: d d u
3: d d u d d u u
4: ddu d duu d ddu u duu
With the information organized like above, I was able to find that the very first d we got for 1st fold was present in the middle section of each of the folding we did up to 4th folding. From the first to the second fold, we see that adding d in front of d (from 1st fold) and u after d (from 1st fold). Likewise, from the second fold to the third fold, we add d in front of d and u(from 2nd fold) and u after d and u(from 2nd fold). But I realized that it is hard to explain in words. Colouring d and u to represent my explanation of the work was a better way.
Red d represents d from 1st fold
Orange d and u represent d and u that were added during 2nd fold
Green d and u represent d and u that were added during 3rd fold.
Black d and u represent d and u that were added during 4th fold.
1: d
2: d d u
3: d d u d d u u
4: ddu d duu d ddu u duu
As we go on, we add d in front of d and u that were added just before and add u after d and u that were added just before.
With this approach, we can find the d, u patterns for 5th fold, 6th fold, 7th fold and so on. But then, it is really hard to find the d, u pattern for 100th fold or 250th fold just with thinking recursively and thinking symmetrically. However, using Python 3 program, we can write the code and execute to get the patterns for 100th fold and 250th fold. Of course, human can get the patterns for 100th fold and 250th as well, but it takes much time and errors may occur during the process. So I tried my best to come up with mathematical expression for this pattern. However, I was not able to as this gets more complicated as the number of fold increases.
4. Looking Back
My solution for this question is correct as this clearly demonstrates the approach and the result. My argument for this claim is correct as I have tried number of folds from 1 to 4. With these as supporting evidence, we can conclude that the patterns for the next fold follows just like what I demonstrated above. I can also check the result for 5th fold and compare the result with the expected 5th fold value I generated using the patterns I found.
Expected Values for 5th fold generated using the patterns I found
5: ddu d duu d ddu u duu d ddu d duu u ddu u duu
Result I got by folding and recording for 5th fold:
5: ddu d duu d ddu u duu d ddu d duu u ddu u duu
These two shows exactly same patterns. With this, we can conclude that my argument is correct.
The problem with this approach is that it is very difficult to generate the pattern for 1000th fold as we have to do this starting from 1st fold and go on to reach 1000th fold. We cannot use this solution for other problem. This solution is only for the paper folding problem. However, the approaches I took can be used in various Computer Science problems.
Solving this problem has enabled me to review Polya's Method once again to analyze and approach the problem in Computer Science.
This week, we learnt about proving worst case and it was quite easy as it was similar to proof I have done before during the last week to prepare for the test.
Paper Folding (Problem-solving Episode)
This week, I would like to demonstrate my Polya's Method on Paper Folding problem that we did previously during the lecture. This is done to reinforce and check my understanding and approach to solve the problem.
1. Understanding the Problem
What we know is that using a paper strip, as we fold one by one, we have to find a pattern on how crease points being vertex up or down differ. I decided to label vertex up crease point as u and vertex down crease point as d. In this question, the condition is that when we fold the paper strip, one end of the strip has to meet the other end of the paper strip. If this condition is not met properly, then the result for the problem would become messed up. We have to come up with a method where we can exactly predict the fold pattern just by looking at the number of fold it has been done on the paper strip. To do that, I first thought that I could try some of the very first few folding to analyze the pattern. The unknown is the pattern that corresponds to the specific number of fold.
2. Devising a Plan
The first plan I came up with is that I try folding up to 4 times and observe whether there is any similar patterns among all these folds I have done. Next, I will record crease point vertex up and down for every folding I did. With the data collected, I will organize the data in a way that I can analyze its pattern. Then, I will try what I need to put in addition in the sequence from the first fold to the second fold. Then I will do the same thing with the second fold and the third fold and so on. Also, I will also count the number of d and u for every fold I do to analyze the pattern.
3. Carrying out the Plan
I exactly carried out the plan I devised and got the results shown below.
1st fold: d
2nd fold: d d u
3rd fold: d d u u d u u
4th fold: d d u d d u u d d d u u d u u
Just with this information that is organized like this, I was not able to find out whether these folds even have patterns or not.
I tried approaching the problem by counting the number of d and u present for each folding.
1st fold: 1d
2nd fold: 2d 1u
3rd fold: 3d 4u
4th fold: 8d 7u
However, I quickly realized that my devised plan is wrong for this part as counting the number of d and u present in the fold does not tell us anything about the patterns.
Hints for this question were given. Hint #1 was thinking recursively. Surprisingly, hint #1 was exactly what I did up until now. I approached the problem recursively. However, the problem with my approach was that I only thought that d and u would be added up to the start and end point of the folding patterns. Hint #2 was thinking symmetrically. This hint sparked my mind. With hint #2, I started to look symmetrical pattern, I immediately organized the above information like below.
Numbers 1, 2, 3, 4 represent the number of fold.
1: d
2: d d u
3: d d u d d u u
4: ddu d duu d ddu u duu
With the information organized like above, I was able to find that the very first d we got for 1st fold was present in the middle section of each of the folding we did up to 4th folding. From the first to the second fold, we see that adding d in front of d (from 1st fold) and u after d (from 1st fold). Likewise, from the second fold to the third fold, we add d in front of d and u(from 2nd fold) and u after d and u(from 2nd fold). But I realized that it is hard to explain in words. Colouring d and u to represent my explanation of the work was a better way.
Red d represents d from 1st fold
Orange d and u represent d and u that were added during 2nd fold
Green d and u represent d and u that were added during 3rd fold.
Black d and u represent d and u that were added during 4th fold.
1: d
2: d d u
3: d d u d d u u
4: ddu d duu d ddu u duu
As we go on, we add d in front of d and u that were added just before and add u after d and u that were added just before.
With this approach, we can find the d, u patterns for 5th fold, 6th fold, 7th fold and so on. But then, it is really hard to find the d, u pattern for 100th fold or 250th fold just with thinking recursively and thinking symmetrically. However, using Python 3 program, we can write the code and execute to get the patterns for 100th fold and 250th fold. Of course, human can get the patterns for 100th fold and 250th as well, but it takes much time and errors may occur during the process. So I tried my best to come up with mathematical expression for this pattern. However, I was not able to as this gets more complicated as the number of fold increases.
4. Looking Back
My solution for this question is correct as this clearly demonstrates the approach and the result. My argument for this claim is correct as I have tried number of folds from 1 to 4. With these as supporting evidence, we can conclude that the patterns for the next fold follows just like what I demonstrated above. I can also check the result for 5th fold and compare the result with the expected 5th fold value I generated using the patterns I found.
Expected Values for 5th fold generated using the patterns I found
5: ddu d duu d ddu u duu d ddu d duu u ddu u duu
Result I got by folding and recording for 5th fold:
5: ddu d duu d ddu u duu d ddu d duu u ddu u duu
These two shows exactly same patterns. With this, we can conclude that my argument is correct.
The problem with this approach is that it is very difficult to generate the pattern for 1000th fold as we have to do this starting from 1st fold and go on to reach 1000th fold. We cannot use this solution for other problem. This solution is only for the paper folding problem. However, the approaches I took can be used in various Computer Science problems.
Solving this problem has enabled me to review Polya's Method once again to analyze and approach the problem in Computer Science.
Saturday, November 1, 2014
CSC 165 SLOG #7 (Week 8)
This week was quiet tough for me as I had to complete both assignments from CSC 108 and CSC 165. However, as I already started these last week, I was able to manage my time to study for CSC 165 term test as well. Floor function limit was a bit confusing for assignment 2 in the beginning, however, I managed to learn and was able to understand the problem clearly. One thing I am sure of is that every course at UofT has gotten more difficult compared to the beginning of the term. However, I will keep trying my best to achieve marks that I desire.
This week, I learnt about the worst case and big-oh of the case. Understanding the proof of
Wis ∈ O(n2) was the hardest proof I have seen in this course. Bounding a sort part was quiet easy to understand compared to the proof. The general proof structure was easy to understand as well since I already had much experience gained from the assignments. Then, during Wednesday's lecture, I learnt the proof of Wis ∈ Ω(n2). It was easier than the last lecture as I already previewed the lecture slide to better understand the lecture.
Big oh can be used when the time taken for the algorithm to execute command depends on the amount of information the programming it has to read. If there is too much information, the programming will take longer time to execute. O(n2) is such that its performance depends on square of n where n represents the amount of information input we are putting through the algorithm.
What I am worried about is not assignment 2, but term-test that I have next week. Although I did practice and review the lecture slides, proving Wis ∈ O(n2) and Wis ∈ Ω(n2) are still challenges for me. Other than that, I am ready to write my test next week.
This week, I learnt about the worst case and big-oh of the case. Understanding the proof of
Wis ∈ O(n2) was the hardest proof I have seen in this course. Bounding a sort part was quiet easy to understand compared to the proof. The general proof structure was easy to understand as well since I already had much experience gained from the assignments. Then, during Wednesday's lecture, I learnt the proof of Wis ∈ Ω(n2). It was easier than the last lecture as I already previewed the lecture slide to better understand the lecture.
Big oh can be used when the time taken for the algorithm to execute command depends on the amount of information the programming it has to read. If there is too much information, the programming will take longer time to execute. O(n2) is such that its performance depends on square of n where n represents the amount of information input we are putting through the algorithm.
What I am worried about is not assignment 2, but term-test that I have next week. Although I did practice and review the lecture slides, proving Wis ∈ O(n2) and Wis ∈ Ω(n2) are still challenges for me. Other than that, I am ready to write my test next week.
Friday, October 24, 2014
CSC 165 SLOG #6: (Week 7)
This week, our class covered how to disprove once again. I had a quiz as usual and I think I did pretty well on this quiz. The quiz was on about proof. I think this week's quiz material was related to learning how to structure a proof 2 weeks ago. My progress on studying proof is going well as I practice proving various problems 3 times a week.
Professor Heap also announced that Assignment #2 is posted online now. I guess it is time for me to start on CSC 165 Assignment #2. The first assignment was a success as I achieved A on the assignment. However, I would like to aim higher and achieve above 90%. When I first enrolled in CSC 165, I expected that it would be so difficult and boring that I have to study all night. However, right now, CSC 165 is the most interesting course during my first term at U of T. It has changed my perspective on how I look at the problem. CSC 165 has also enabled me to dream of becoming an Artificial Intelligence specialist. When I first started Computer Science at U of T, I just wanted to become a computer scientist. However, as I take CSC 165, I have found various interesting and specific details about computer science.
For this week, allowed inference part of the lecture was most significant lesson to me for this week. There are many types of inferences that are available to us to prove the claim.
I would like to list various types of inference I have studied during Professor Heap's lecture.
- Conjunction elimination
- Existential instantiation
- Disjunction elimination
- Implication elimination
- Universal elimination
All these techniques were the ones we used to prove various types of question during the lecture.
On the lecture slide named 'more inferences' by Professor Heap, it introduces what other inference exists.
These are implication introduction, universal introduction, existential introduction, conjunction introduction and disjunction introduction which I already understand well enough.
I also attended Larry Zhang's lecture to learn more about proof. I learnt that introduction is used to infer from smaller statement to larger statement whereas elimination is used to infer from larger statement to smaller statement.
Then we learnt about sorting algorithm. Sorting algorithm is very important as this is a fundamental for software programming. When I was in grade 11, I studied programming, but I never knew the importance of the algorithm. All I cared about was learning programming at that time. However, taking CSC 165 enabled me to realize the importance of algorithm in computer science. Although I found learning sorting algorithm a bit hard, I already knew a bit as I learnt Python programming language.
There are two types of sorting algorithm. These are insertion sort and selection sort. Professor Heap also told us that for this class, we will focus on learning algorithm speed and care 'worst' specifically. He said that average of algorithm speed is important, but he told us that we still do not have a strong background to learn that.
I think taking CSC 108 sometimes helps me understand the content of CSC 165. As I learnt how to program in Python, I understood what the code posted on the lecture slide meant.
Despite the content of CSC 165 is becoming more rigorous, I feel confident that I can do it. Let's study CSC 165!
Professor Heap also announced that Assignment #2 is posted online now. I guess it is time for me to start on CSC 165 Assignment #2. The first assignment was a success as I achieved A on the assignment. However, I would like to aim higher and achieve above 90%. When I first enrolled in CSC 165, I expected that it would be so difficult and boring that I have to study all night. However, right now, CSC 165 is the most interesting course during my first term at U of T. It has changed my perspective on how I look at the problem. CSC 165 has also enabled me to dream of becoming an Artificial Intelligence specialist. When I first started Computer Science at U of T, I just wanted to become a computer scientist. However, as I take CSC 165, I have found various interesting and specific details about computer science.
For this week, allowed inference part of the lecture was most significant lesson to me for this week. There are many types of inferences that are available to us to prove the claim.
I would like to list various types of inference I have studied during Professor Heap's lecture.
- Conjunction elimination
- Existential instantiation
- Disjunction elimination
- Implication elimination
- Universal elimination
All these techniques were the ones we used to prove various types of question during the lecture.
On the lecture slide named 'more inferences' by Professor Heap, it introduces what other inference exists.
These are implication introduction, universal introduction, existential introduction, conjunction introduction and disjunction introduction which I already understand well enough.
I also attended Larry Zhang's lecture to learn more about proof. I learnt that introduction is used to infer from smaller statement to larger statement whereas elimination is used to infer from larger statement to smaller statement.
Then we learnt about sorting algorithm. Sorting algorithm is very important as this is a fundamental for software programming. When I was in grade 11, I studied programming, but I never knew the importance of the algorithm. All I cared about was learning programming at that time. However, taking CSC 165 enabled me to realize the importance of algorithm in computer science. Although I found learning sorting algorithm a bit hard, I already knew a bit as I learnt Python programming language.
There are two types of sorting algorithm. These are insertion sort and selection sort. Professor Heap also told us that for this class, we will focus on learning algorithm speed and care 'worst' specifically. He said that average of algorithm speed is important, but he told us that we still do not have a strong background to learn that.
I think taking CSC 108 sometimes helps me understand the content of CSC 165. As I learnt how to program in Python, I understood what the code posted on the lecture slide meant.
Despite the content of CSC 165 is becoming more rigorous, I feel confident that I can do it. Let's study CSC 165!
Subscribe to:
Posts (Atom)