CSC SLOG #12: Last Week before the Final Exam

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.

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!

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!

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 2ⁿ ∉O(n²) 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 -> ∞) 2ⁿ / (n²)

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 -> ∞) 2ⁿ ln2 * ln2 / 2

Then we can show this as shown below. 

∀c∈ R⁺,∃n_c∈ N, ∀n∈ N, n >= n_c -> 2ⁿ/n² > 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.

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.

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(n²) 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 ∈ Ω(n²). 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(n²) 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(n²) and Wis ∈ Ω(n²) are still challenges for me. Other than that, I am ready to write my test next week. 

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!

CSC 165 SLOG #5: Prove/Disprove (Week 6)

I just finished studying week 6 materials for CSC 165. On this Wednesday, I got my score for CSC 165 term test 1. I was satisfied that I got 90% on my very first test. Hooray! When I looked over my test to find out what I got wrong, it seems like I had hard time explaining the last question of the test. However, I am glad that my first test was not a fail. I feel confident that my score on the test shows how much effort I have put into CSC 165. Mathematical logic is not about memorization. It is all about practice. As I practiced for the test, I was able to explore more deeply on CSC 165. Learning proving and disproving was not that hard. Even limit proof was not a challenge to me. In fact, I was able to understand it at first glance. I am very eager to learn proof in depth to enhance my skills as an amateur computer scientist. I am glad that I finished half of my first term with success at U of T. Now I have my one last midterm test which is Mathematics. I guess I have to spend more time on Mathematics just like how I devoted more time on CSC 165 for the term test. Time to study Math!

CSC 165 SLOG #4: My first test (Week 5)

Now it is Week 5 of CSC 165. This Wednesday, I had my first term test for CSC 165. This term test was also my first test at U of T. I think the best way to study for the test was to practice solving the past exam. As I solve little by little, I started to understand and know how mathematical logic plays a role in our lives. Not only that, mathematical logic is very significant in computer programming as we have to understand how computers' function works. But what I had the most problem was translating from symbolic logic to English or vice versa. I think it is because I was confused with the difference between implication and conjunction. Before learning about implication and conjunction in CSC 165 lecture, I always thought of them equal or very similar. However, as I learnt CSC 165, I came to realize that these two represent totally different things. I think solving Assignment #1 was also a big help for me to study. What I also found interesting was that doing CSC 165 SLOG also assists me in my study with mathematical logic. I feel like doing my SLOG is like my review for the course materials we covered. Not only that, SLOG made me realize how I have to prepare for assignments and tests. I hope I can achieve high marks on my term test. I have learnt a lot for five weeks and I am eager to learn more about mathematical logic.

I would like to demonstrate my ability in translating from mathematical logic symbol to English.

I am going to let X as the domain of all games and point, G as game, P as point, C(x,y) as x contains y and F as fascinating. 

Symbols: ∀x∈ X, G(x) -> (¬∃y∈ X, P(y)∧C(x,y)∧ F(y))

English: Every game contains one fascinating point.

For this week, we learnt about proof. I think proof is one of the most essential parts in Computer Science. Up until now, I learnt about the basic of mathematical logic to prepare to learn about proof. When I first encountered proof in CSC 165, I was surprised. I always thought of proofs that I learnt during Mathematics class. However, in this course, we learnt how to structure our proof. This was also on the quiz that I took this week. I feel like proof is going to be a tough challenge to me. I hope to master the beauty of proving and disproving statement.

On Friday, I learnt that I can prove the problem in various ways. But I think I still need to practice how to prove something false as I get lost in the midway of proving. To overcome this challenge, I decided to review during the weekend. I already went over CSC 165 notes that I took this week. But if I look at it again during the weekend, I think I can understand the content of the lecture better than last time. It's like reading same books over and over again. Reading multiple times always allowed me to interpret the content much better and easier. I will try my best learning how to prove an implication.

But what interests me the most is how proving and disproving play a role in our real lives. Proving is the most significant area in computer science. But how about in art, history or physics? I hope to learn how these skills I learn is used not only in computer science but also in other areas like arts. Even if it may not be related with subjects like art, it still plays a huge role in Computer Science, Mathematics, Commerce, Economy which affects our daily lives. As I learn CSC 165, my way of viewing the world has changed. CSC 165 is such an amazing course.

CSC 165 SLOG #3: Another Challenge (Week 4)

As I start a new week, I began to find CSC 165 more challenging than before. Double quantifiers were the hardest material for me to understand. Despite I read over the notes again, I still found the material I learnt this week as challenging. What I found easy was the tutorial and the quiz I had this Tuesday. De Morgan's Law and transforming -> to (not) and (or) for equivalence was the easiest thing I did this week. I was able to understand very quickly. I hope to get 2/2 on this week's quiz.
To demonstrate my understanding on De Morgan's Law, distributive law and etc, I decided to solve one equation that I made it myself.

P(x) → Q(x)∧R(x) <->¬P(x)∨(Q(x) ∧R(x)) 
                            <->(¬P(x)∨Q(x)) ∧(¬P(x)∨R(x))

What I found interesting was that as I practiced for the tutorial, I get used to tranforming and using De Morgan's Law.

However, the proof was another obstacle that I had to overcome. The concept of approaching to infinity was easy since I already learnt that in Math. However, other proof to prove various mathematical expression was so confusing to me.

Learning transitivity was easy as I was able to understand in one glance. The professor has given us an example for transitivity which is shown below.

∀x∈ X, (P(x) → Q(x)) ∧(Q(x) → R(x))

Not altering the truthfulness was very challenging for me and I had so much problem to understand that. As we explore more on logic and mathematical expression, it gets more challenging. 

Last thing I want to talk about is CSC165 Assignment #1. I worked with one other person to complete the assignment. Question 4 on assignment was very challenging to me, because at first, I thought that there should 3 sets existing. However, I realized that one set is universal set and two sets are within the universal set. Negation and changing symbolic form to English and vice versa was very easy to me as I have already practiced a lot during the last weekend. I hope that I do well on this assignment, because I believe the first assignment should be the easiest one among three assignments. 

Now that I have my first CSC165 mid-term test coming up, I plan to study 5 to 6 hours over the weekend. Although I have already been studying for the test, the practice makes perfect. So I will keep putting my effort into study. Let's do this! I hope to achieve high marks!

CSC 165 SLOG #2: More about logic, conjunction and disjuction (Week 3)

This week, we went over the materials in the course faster than usual. It was quite hard for me to understand the material, so I had 1 hour of review time after the lecture sessions. I first learnt about natural language again which I am very familiar with due to my practice on this topic last week.

The professor told us that when we see 'unless' in English, translating it to 'if not' will make our understanding much easier. I also learnt about idiom which was fairly easy.

I also learnt about conjunction and disjunction. One is "and" and the other is "or" These are materials that I already learnt in high school.

For A(x) and B(x) to be true, both of them have to be true. If there is any counter-example to this claim, the claim is false.

For A(x) or B(x) to be true, at least one of them has to be true. If there is no true example, then the claim is false.

I made a chart to demonstrate symbol versions for 'and' and 'or'.

	And	Or
Union Symbol	∩	∪
Logical Symbol	∧	∨

The logical symbol for 'And' is called caret and 'Or' is called reversed caret.

Both union and logical symbols are acceptable as they have the same meaning.

The professor also taught that English can be tricky for conjunction and disjunction. There are inclusive and exclusive. Inclusive means X or Y or both whereas exclusive means X or Y, but not both. This was very interesting to me as there is no inclusive and exclusive situation in Korean. When we want both X and Y, we say X and Y. But if we want X or Y, we say X or Y.

Next thing we learnt is negation symbol which is ¬. The symbol means not. I thought I am fine with the negation until I faced special negation idiom part.

The professor gave us the expression shown below. I will number that expression as 1 to be clear.

#1. ∀x⊆X, P(x) ->Q(x)

Let's call the negation of expression #1 is expression #2

#2. ∃x⊆D, P(x) ∧¬Q(x)

What I first expected for the negation of expression #2 was back to expression #1. However, the professor showed us that the negation of expression #2 is not expression #1, but new expression. Let's call that new expression #3.

#3. ∀x⊆D, ¬(P(x) ∧¬Q(x))

This surprised me quite a lot. However, as I tried solving them, I realized the reason why the negation of expression #2 is not #1, but #3. Then the negation of #3 expression is back to #1. As I learn more about logic, it is getting more confusing and interesting.

Going over truth table part was easy. However, what interested me was how 4 sets would look like in the standard Venn diagram. It would have 2^4=16 regions. However, I wasn't able to draw it properly. Drawing 2 or 3 sets is easy whereas 4 sets is so hard.

As I learn more about logic, my way of thinking and dealing with problem has been improved. I hope to expand my knowledge on logic in CSC 165.

CSC 165 SLOG #1: Report on my accomplishment

I just finished studying on how to distinguish which one is antecedent or consequent. I spent 2 hours with my friend to study this topic and tutorial #2 yesterday. Then  I spent 2 hours studying for natural language, tutorial #2 and previewed the next coming-up lecture today. Now that I have put enough effort, I feel more confident in CSC 165 course. I guess practice always improves people's skills. One thing I found is that studying with friends is an efficient study technique. Both my friend and I concentrated on studying and discussed things that we do not understand. I hope to learn more in CSC 165!

CSC 165 SLOG #1: My first SLOG for CSC 165 Fall! (Week 1 and 2)

Not only is this my first SLOG, but also this is my first time making my own blog!

I had my first tutorial yesterday which was fairly easy compared to other course. It was about Venn diagram and how we can prove whether the universal and existential claim are true or not. We also went over the meaning of  ∀ and ∃.
∀ represents for all.
∃ represents for some.

The symbols were easy as I have already learnt it during high school.

I summarized it below on how to verify universal and existential claims.

For universal claim to be true, we need to check that all the examples given are true to the claim.
For universal claim to be false, we need at least one counter-example.

For existential claim to be true, we just need at least one example that supports the claim
For existential claim to be false, we need to check that all the examples provided must be counter-examples to the claim.

Verifying universal and existential claim is very fun to me. I also took my first quiz in CSC 165 and hope to achieve high score on it.

Today, I explored the topics of implication, converse and contrapositive which were new to me. Not only that, I also learnt about expressing implication in English just like shown below.

Implication: P ---> Q
Expressing implication in English: "If    P  , then   Q   ".
Where P is antecedent and Q is consequent.

But that was when I faced my first challenge in the course.

During the lecture, I had hard time figuring out which one is antecedent and consequent for each statement. That was when I realized that this course is the most confusing. The course material itself is not that hard, but I find it very confusing. In order to overcome this challenge, I decided that I will practice on distinguishing between antecedent and consequent from natural language this week. I am aiming to master today's material by this week. To check my achievement, I am going to put another post on this Sunday to see how well I have done according to my plan. If not, I will try to find some improvement with my plan to achieve success in the course.

At the end of the course, I hope to achieve more skills in order to be a computer scientist and to explore computer science.