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.