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.