Slog for week Nov. 24

What's new?

This week we are going further on stuff about computability theory from last week. First of all, the idea that every listable set is countable make me clearly understand what is a countable set. To make sure a set is countable, we can just make a list of input and a list of corresponding output, then if there're no identical output and input, then the set is countable (since it satisfied both onto and 1-1 at the same time).

Then, we've talked about induction. Induction is quite understandable for me since I'm taking MAT 137 right now and the approach is normally using in mathematical proof.

Questions & concern:

1. On the lecture, I'm quite confused that what is UTF-8?

2. I'm quite confused about countable and computable. Under my understanding, countable is related to sets, however computable is related to functions. Is it correct? Is there other way to distinguish these two words in logic?

3. I'm quite confused about Friday's lecture. Are there any questions on final exam related to the knowledge on Friday's lecture?

slog for week of Nov. 17

• What's new?

          This week's a short week, but stuff for this week is totally new and super difficult for me I think. And honestly, I'm very confused about what we've learnt in this week. A totally new concept - computable and non-computable, had been introduced to us, through the example function, halt. 

          Then we've learnt about finite sets. This part is more understandable i think, especially the concept of 1-1 and onto cause they've been introduced in other math courses like MAT223 and MAT137(something related to other courses). Thus I can understand whynot 1-1 will result over-count and not onto result undercount. And we have the conclusion: every set which is smaller than natural number set is always countable. 

• Problem?

          1. I'm not quite well understand the halt function and navel_gaze function which were talked about on Wednesday's lecture. What makes them become non-computable function? And how I can distinguish a given function is computable or not?

          2. Friday's lecture, our prof said set of rational number has the same size to the set of  natural number. I'm questioning why? 

          

Slog for Week Nov. 10

• What we've learnt for this week?

          This week we've learnt how to prove and disprove a given function is in big-Oh and big-omega. After this week's lecture, through reading the given proof example by our instructor, I found that I clearly understand the meaning of break-even point(B) and my confuse from last two week, about how to choose B, has been solved.

          Another new concept from this week is about F (general statement about two functions). This part is very challenged for me indeed, but through instructor's note, I think I'm kind of understanding how to prove (but obviously I'm still not proficient on proving this kind of questions, thus I still need more practices).

• Confuse and challenge:

1. As I was proving Big-O, I carefully write down the statement we want to prove. Then, I realize when two functions is coinciding as variable'n'  become infinitely big, then one of the function is still in Big-O of the other function. So why? Obviously the second function is not larger than the first function anymore. 
2. One of the example question is using  limit and l'Hôpital's rule. So I'm confusing are we allow to write some scratch work about limit and l'Hôpital's rule first, then start our actual proof below it?  

Slog for Week Oct. 27

We’re going further on the topic of sorting method and big O/omega. But as we’re moving on, I’m getting more and more confused about this chapter’s topic.

1. While we are counting the running steps of a program, if a statement is false (like while loop, while n<100, and now n = 101), is it still counting as 1 step?
2.  I’m not quite understanding the big O, particularly the Breakpoint B. As we are making a proof of big O, what kind of number we should take for B? (as specific as possible)3.       When I’m counting steps, I usually struggle on this kind of problem:
3.     .     When I’m counting steps, I usually struggle on this kind of problem:

so as we’re counting running steps of a while loop inside a while loop, is it the easiest way to start from the inside while loop?

Slog for Week Nov. 3

• What's new? & Problem

      This week’s lecture is more understandable than last week I think. That is because we start focusing proving the Big O/omega, instead of counting steps and working with a series of number. It seems easy because we just need to remember the statement of Big O and following the structure of proof we’ve learnt before. But there’s still an easy question: why B and C have to be nature number instead of any positive real number? 

Slog for Week Oct.20

• What's new and some problems:

    On this week’s lecture we’ve ended the chapter of Proof by introducing some inferences. These inferences briefly and clearly show us how to prove in some situations and what should do next if we’ve already assume everything.  Additionally, some sorting methods, such as insertion sort and selection sort have been mention in the lecture. Because I haven’t learnt these sorting methods before, I’m feeling very confused about which method is the best and which one takes the least steps if I have a very large input. Besides, I’m still confusing about when I should use linear search and when should use insertion sort/selection sort.