Week 12: Assignment 3

I know this Slog is a little bit late, and today is the due date of assignment 3. Last week, I, along with our group members, had been working on this assignment for a long time, although many of them are not so hard.

First, I want to talk about some points that we need to notice when we are typing our answer into computer. Although I do not know how to use LaTeX, I believe that the equation tool (not equation editor) in Word is enough for our use. We already know that "\forall" is ∀, while "\exists" is ∃. Something we might not know is how we type the symbol for a set of functions in question 4, ℱ. The "code" for this is "\scriptF". After googling it, I noticed that curly F is usually used as symbol for a set of functions. Another thing is the big-Oh. Noticing that it's not simply "O", but "𝒪", I just tried "\scriptO", and that is it. By the way, big-Omega is just big-Omega.

Now is the important things. I think the most difficult one should be question 5, we felt that this claim is false, and tried to find a counter example. First, we chose f(n) = n, g(n) = n + sin n, because f and g intersect with each other forever when n becomes larger. Unfortunately, if we multiply either f or g with a c, they will never "meet" when n is large, so this is a wrong answer. Actually, this was a stupid mistake, since both f and g we chose are in θ(n), they must be in each other. 

Maybe it was because there was a sine in our first try, we kept choosing functions with sine in them. Finally, we figured out two functions. The point when choosing functions is that, when we multiply c with the function, the lower bound of its range should not increase. f(n) = sin n + 1, but still, this is not the answer, because it is quite difficult to find an integer n such that sin n equals to -1 to make f(n) be zero. So we slightly modified f(n), then it looks like f(n) = 1 for all odd numbers, and f(n) = 0 for all even numbers. 

Today, I just found another function that is similar to the one that we used in the assignment. The basic form is f(n) = arcsin sin n. Also, we need to make some little changes to satisfy the property.

Other questions are not such difficult, I hope we won't lose points on them.

In addition to the assignment 3 that I focused on this week, I also found a slog impressive this week, where the author using flow chart to illustrate how the halt function works. Flow chart is what I learnt in grade 11. Actually why halt is not computable has been confusing me for a long time. This chart really helped me a lot.

Week 11: A Taste of Computability

I thought computer can do everything, but this week's lecture told me that was not true.

A computer can solve problems if you give it an algorithm. So, if you tell it how to solve those problems, it will give you the answer to the question. No matter how complicated the algorithm is, computer will keep calculating until finish. However, what if you cannot provide an algorithm? Here, I learnt two terms, "well-defined" and "computable". If you say that a function is well-defined, then no matter what your input is, you can tell what the output is (but maybe you don't how you get the output). If you say that a function is computable, first, it must be well-defined. Second, you should be able to tell how do you get the output from the input.

For example, we can assume a simple example. Assume f(x) = 2x, then f(x) is well-defined because for each x in its domain (R), we can tell what f(x) is. Also, it is computable, because we just need to multiply 2 with our input to get the output. The first time I got here I got confused. Is there any function that is well-defined but not computable? I was convinced that there is, and actually there are plenty of them. Assume halt(f, n), which is a function that returns True if function f(n) (input) halts, else return False. Then it is well defined, because for each input, we can tell the output. However, we cannot tell how we get that. If it does not halt, you will never return a value.

We use a strategy called reduction to prove many other functions are all not computable. (And question 5 in assignment 3.) I think we can reach it deeper next week.

After reading a student's slog, I recalled something we learnt last week. In that slog, he focused on the δ-ϵ definition of limit. In the end, he said "Before the  (ε, δ) definition comes out, Newton, Leibniz can't give a precise statement; the very reason because they can't explain infinite small." This is exactly what I heard last year when learning calculation. At that time, we learnt infinite small first, and then learnt the definition of limit using the definition of infinite small rather than the δ-ϵ definition. Last year, the teacher said the δ-ϵ definition was hard for beginners (as the author of this blog said), so we changed the way of learning the limit. Now I have a new sight of the definition of limit from to different but similar angles.

Week 10: Test Two and Chapter Four

I thought chapter four is something easy before because I have been using big-Oh since grade ten. Today, I have changed my view. I saw it easy just because I can judge a program as O(n^2) if there is a double loop. However, everything will seem hard when we learn it in mathematical language. It is a rigorous method to prove something.

This week for chapter four, we did more on proving big-Oh and big-Omega. The point is still how to choose c and B. Basically, for polynomial functions, we can just choose B = 1, which is a magic breakpoint. Then we underestimate the larger side of the equation, and overestimate the other side. Finally, we can get f(n) >= c * g(n) or f(n) <= c * g(n). 

Overall, we are proving with specific numbers. What about more general things? First, we want to define the set of functions that we are doing so far. They are all like, input a natural number and output a positive real number. Then define their set as F:{f: N-->R+}. Now, we can prove general things by choosing functions from this set. The most important thing is still how to wisely choose c and B, which mostly related to other c's and B's.

Basically I'm (quite) happy that chapter four is over because it's the most difficult part so far. (Of course everything gets harder and harder.) Meanwhile, I delighted that I got 29 in test 2, which actually I think I deserved. 

My friend posted something that really enlightened me in this week's blog where he said that "when finding upper-bound, it is OK to over-estimate the number of steps" and "when finding lower-bound, it is OK to under-estimate the number of steps". Professor Heap might mentioned this during lecture, but I think I missed them. Anyway, these ideas teach us what to do when proving some function is in O(something). We can say n^2+2n+1>n^2 or n^10-n^6<n^10, which is how we prove them.

Week 9: Test II

Talking about test 2 reminds me of the first test, which I got only 30/38 but still believe I didn't do anything "wrong". Well, forget about that (because it is only 1.32 points in the final score), I believe (hope) I did well in the second test.

The format of this test, again, is very similar to the one from the old sample test. To my surprise, there are two question that are about the definition and proof of floor function. However, the third question very similar to the claim 1.4 in the assignment 2. After we had a group chat last Wednesday, we finally figured out how to solve claim 1.4. At the beginning, we tried to prove it by assuming its negation is true, which I think is not a common way that we are taught in the class. So finally, by finding a good z, we proved it directly. The test is quite similar so I just write nearly without thinking.

Unfortunately, I believe I made a mistake in the second question. I chose d = e + 1, and then use the third part of the definition by letting z = d. However, d that I chose is not an integer! If I choose d = floor(e) + 1, things would have been solved! I hope this is not a big deal, and I can still get most points of this question...

For the lecture part, I was like having been sleeping for a whole hour (but actually not), because I found it so hard to understand what the professor just said. Luckily, my classmate told be to check out the slides of Professor Larry Zhang. The truth is, they are amazing. Everything is so clear and sometimes funny. Now I am pretty confident that I can learn pretty well in this chapter.

Week 8: Counting steps and Big-Oh

I have heard of the big-O for a long time, maybe first time in grade 10. At that time, all I knew about it is that it is a tool to measure how fast a program can finish a task. Well, after this week, I have a new understanding of big-O.

Before learning the definition and how to use big-Oh to justify a program, we need to first learn how to count how many steps a program will take. Basically, the outer part of a program, that is, the part not in any loop, will be executed once. If the sentences are in a loop, to calculate the worse case, just multiply the number of steps in the loop with the maximum time the loop will be executed. For example, if there are two sentences in a while loop, and the loop will be executed three times, then the total number of steps should be 2*3=6. Moreover, loop in loop has the same method to calculate.

I think result of counting steps does not have to be unique because you cannot tell how exactly which case the program will choose. And according to the note of the professor, sometimes we just regard 1+2+...+n steps as n+n+...+n=n^2 steps, rather than n(n+1)/2. I think maybe the reason for this is explained when we learn big-Oh later.

Well, big-O is indeed a "tool" to measure a speed of a program, but not like human who measure speed by testing how many things a program can do in one second, it shows us how many steps a program will take to finish a task. More strictly speaking, it tells us how the number of step of that program changes when the input of the program increases. For example, if I want a program to find a book among 100 books, it will take some steps. But if I want it to find another book in 500 books, how many steps will it take? We can say the program is more quickly if the amount of steps doubled than if it was squared. This actually just explained why n^2 and n(n+1)/2 is the same in big-O. When input doubled, the number of steps both squared, with no difference.

Test two is coming, while I read this in a student's slog: "We are not told if we are allowed to bring aid sheet so that I did not prepare one." I think we have been told for several times that we can bring an 8.5*11 aid sheet at the beginning of the lecture. Also, I don't even think an aid sheet is useful. The questions in the test are quite similar to the ones of previous years. If we review them (even not carefully), you can get a good grade. Meanwhile, there is nearly no equations that we need to use during the exam, I'd rather spending time on reviewing other subjects than writing aid sheet.

Week 7: Penny Piles

On Friday, we have an interesting lecture. The topic is called penny piles, which means, if you have 64 pennies in a drawer, and 0 in another drawer, every time you can move half of the pennies from one drawer to the other if and only if the drawer has an even number of pennies. When a drawer has an odd number of pennies, the game stops. And the final question is, can you get any number (less than 64) of pennies in a drawer?

My first guess is yes, but I can't tell why, so I started to try. I assumed that there are only eight pennies in the first drawer rather than 64 (which is exactly the second hint). For the first try, I move four pennies to the second drawer, so its 4-4. Again, half to the right and get 2-6. Then either moving from left to right or vice versa will cause the game stop, which results 1-7 or 5-3. And therefore I got all number from one to eight during the moving.

In this way, I guess no matter there are eight or 64 or for all 2^n (n is N+), we can get any number of pennies less than the total number. For the case of total of 16 pennies, I found it hard to write all the possibles in a single list, because each time of moving, I have two different ways of moving. Then I thought up a method, I draw all possible moving in a binary tree, which is just what we are learning in CSC148 (and is just hint 3).

The result is, I found that if we have total number of sixteen pennies, we can also get one to sixteen pennies, which verified my assumption. Meanwhile, I found that except the last line of the tree of sixteen pennies, all the number is just twice of the number in the eight-penny tree. And the last line of the sixteen-penny tree have 8 elements, which are all odd number less than 16. So although this is not a formal proof, we can be quite confident to say that for total number of 2^n pennies, we can get any number of pennies less than 2^n.

To formally prove this assumption, I think we can use mathematical induction. We test the case of 1, 2, 4 pennies manually and assume that if we have 2^k pennies, we can get 1 to 2^k pennies, then we prove that if we have 2^(k+1) pennies, we can get 1 to 2^(k+1).

Week 6: Test Result and more Proof

I finally got my score for my first test in U of T, which shocked me a lot. I got full marks on the second and the third questions, but I lost 8 points on the first question. Last week after the test, I checked the sample solution posted on the professor's website, and I didn't think I got so many wrong answers! I even didn't find anything wrong in my test.

Although I haven't got my test back, I still don't know what mistake I made, but maybe I can guess part of the reasons. In the second part of the first question, I might failed to explain my answer properly. Since I have never written an exam in English, I probably don't know the right way to explain my answer. But despite that, I will get my test back next week and figure out what happened. No matter what's the reason, either I failed to learn well or just didn't write properly, I'm sure I will do better in the next text!

For the lecture, we learned some more different kinds of proofing. First thing is to prove some claims about the floor function. I think the point here is to use the definition appropriately.
And when we want to prove something is wrong, we just need to prove the negation of the claim is correct.

And for the final part of the week's lecture, I learned how to prove the claim which we need to discuss is by cases. What we need to be careful is to find all the cases and do not lose any of them. Only in this way can we prove the claim correctly.

I viewed the blog of my friend this week, he mentioned that the indentation is very important, which I totally agree. Once I read someone's proof without indentation, I found it really hard to keep pace with the author because the proof is chaotic. When we finish our assignment on computer, using Tab is a good choice to make the indentation.

Week 5: Test and Proof

For this week, we took a test on Wednesday, which I think is not quite hard. The format of this test is very similar to the one of last year. I don't think there will be big problem on this.

For the lectures, we continued to learn how to prove a theorem in a good format.
First, to prove existence, which I think is the easiest, you just need to find a number of something that fit the theorem and then you have finished the proof.
Then, we learned how to prove a claim about a sequence. If there is an "exist" in the claim, just find a number which fits the claim (maybe you can find it immediately or maybe you have to calculate and get the number), then assume the antecedent is correct and try to get the consequence step by step. After get the result, do not forget to write the last few lines of the proof: add "for all" or "exists" to the claim.

Other than proving a claim directly, we can also prove that the negation of the claim is false.

I didn't know that blogger can use LaTeX before I found this student's slog.
Like this:

This is how to prove n square is odd if n is odd, which is not such difficult to prove.
The point is, I still don't know how to type in this cool way in blogger.

Week 4: Many proves

In this week's lecture, the lecture is mainly about proof.

Although we have all practiced how to prove in high school, this week's lecture is a little bit different. When we get something to prove, the first thing to do is to understand the reason that makes you believe what you are proving is correct. Then is to write down the expression. As we all know, the key point here is to be correct and can convince other people.

I have never learnt about the structure to prove something until this week's lecture. First, write the "for all" or "exist" quantifier sentence (I don't know the term to describe that) on the first few lines. Then in the next line or few lines, write the antecedent. What should we notice here is that, since the assumption is kind of like "contains" in the previous sentence in logic, you should leave some space from the beginning of the line, just like the python language (by pressing Tab). After writing down the assumption, you need to focus on the proving. Maybe you want to prove P(x) => Q(x), but usually you can get there immediately, so prove P(x) => R1(x), then R1(x) => R2(x), ......, finally Rn(x) => Q(x). According to the transitivity, you can conclude that P(x) => Q(x).

There is another topic in this week, which is about whether two quantifiers can be swapped. The professor take the definition of limit as an example which makes me feel a little bit like being in MAT137 class. But the point in this class is not to learn the definition, but to learn that if the universal quantifier and the exist quantifier are exchanged, there will be different meanings, and the definition after the change is incorrect. However, it a proposition contains only universal or only exist quantifier, then they can be exchanged and they express the same meaning.

I found that many of us do not use symbols in slog. For example, here. I believe it is quite easy in word to type "\exists" to get "∃" and type "\in" to get "∈". Using LaTeX is also a good choice. Using words instead of symbols is sometimes confusing, and if you don't want to use symbols, you should state the complete sentence. 

Week 3: Negation

In the third week, we learned conjunction, disjunction and negation. At first, it was not hard to understand, because conjunction just means "and", and disjunction means "or". However, the "and" and "or" in logic is sometimes different from their meaning in daily life. When we translate English into logic language, we need to be careful about those difference.

Negation is to negate a statement. We should not only change the latter part of the sentence,  we also need to change ∀ into ∃ and vice versa.

It's new for me that the negation of P(x) => Q(x) can be P(x)⋀¬Q(x). We can understand this in English by saying the opposite of "if P is true, then Q is true" is "P is true and Q is not true". 
PS: P => Q equals to ¬P ⋁ Q, which is difficult to understand. Finally, I figured it out by using an example. If our teacher wins the lottery, then he will buy us a cake. If he doesn't win, no matter whether he buys us a cake, the implication will be true. And if he buy us a cake, no matter he wins the lottery, the implication will also be true. Only when he wins but doesn't buy the cake, the implication is false. So, the truth table is like the one on the last 20th page of the slide.

Another challenging thing for me is the distributive law. Although it's like the distributive law in multiplication [like a(b+c)=ab+ac], it might take some time to get familiar with it when using in logic.

In this student's slog this week, he/she said that the word "several" is confusing in "some courses have several prerequisites" because it can means infinite cases such as three, four, thirty and so on. At first, I have the same feeling. However, I figured it out later. What we need to write is a statement in which a course has two prerequisites. In that statement, we do not tell whether there are more prerequisites for this course, so that is exactly what "several" means. 

Since things are getting harder, hope I can hold it until December.

Week 2: Quantifiers

The topic of CSC165 in the second week is quantifiers.
A language element which generates a quantification (such as "every") is called a quantifier. (From Wikipedia)

Some of the logic symbols like ∀, ∃ were introduced in high school, so it's quite easy to understand those quantified sentences.

In the implication section, I learned how to write an "if..., then..." sentence in math language.
And it was quite interesting to find out that if my mom told me that

"If you eat vegetables, then you can have dessert."

I might also have dessert, because she doesn't mention the case I don't eat vegetables. (Real life is different...)

Actually, we can write the sentence like: I eat vegetables => I have dessert.

We cannot tell whether the reverse and the negation are True, 

so the implication: "I don't eat vegetables => I have dessert" maybe True or maybe False.

However, the contrapositive of a statement is the same as the original sentence.

It's like: "I eat vegetables => I have dessert" equals "I didn't have dessert => I didn't eat vegetables".

They are both True of False.

The most tricky thing in this week must be "only if".

The professor said in the sentence "I'll go if you insist", "you insist" is antecedent, and "I'll go" is the consequent, which is easy to understand.

However, in the sentence "I'll go only if you insist" is on the opposite.

After the discussion with my friend, I finally figured it out.

In the first sentence, we know that You insist => I'll go, but we cannot indicate that if I go, then you must be insisting.

But in the second sentence, "I'll go only in the case that you insist" indicates that if I'll go, then you must be insisting. BUT, I may still not go if you are not insisting, so the reverse (first sentence) is not sure.

It's easy to understand that the phrase "if and only if" equals to "<=>", 

so "if P, then Q" means "P => Q" and "only if P, then Q" means "P <= Q"

(It's just my way to understand these kind of tricky sentences, I'm not sure whether they are technically right, though I think they are right.)

Week 1: Introduction

CSC165 is a course about expression.
In the first week, anything seems normal and not very hard to understand.

At the beginning, the professor showed a slide about the language ambiguity.
Since I'm not an English native speaking, it was a little bit difficult to point out the double meaning of some sentences. Fortunately, I understood that the professor tried to tell us the importance of precision in computer language.

After that, I learned how to write code about sets in python.
It's tricky that we don't write {x for x in S and x > 6} as we say, we use "if" instead of "and".

Then some more hard things appeared.
For example, for "all({x in S2 for x in S1}", it means for each elements in S1, if it is also in S2, then this single judgement is True, if all judgments are True, the the whole statement is True.
For example, S1 = {1,2,3}, S2 = {3,4}. Element 1 is in S1 but not in S2, so the first judgement is False. (Actually we can say the statement is False already) So do element 2. But 3 in S1 is also an element of S2, so we can change the statement into all({False, False, True}).

For the first week in U of T, I am exited and nervous. Courses are not so hard and I have plenty of free time. But since it's my first time to live in a place where people speak English only.
Hope I didn't make lots of grammar mistakes in the SLOG.

Hello World!

This is my first blog here.
Nothing more to speak.
Hello World!