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.