(CSC165)_Nov30_Computability

Starting with introducing the idea about One-to-One and Onto in order to define  |X| = |Y|.  More specifically, Given two sets X and Y, if there exists a well defined function f : X ↦ Y that is 1-1 and
onto, then |X| = |Y|. (Note: the idea of 1-1 and onto is more or less the same as we have learned in Math courses)

Why we want to have this definition? Because it is very helpful for us to understand countability, which is just the "surface" of computability. When counting, we are basically using Natural Numbers. We say the set of Natural Numbers are countable, and then if a set |A| ≤ |N|, then it is countable.

A interesting fact is even if some sets are infinite (e.g. N, or set of odd numbers), they are still countable. So, with the definition, the set of real number should not be countable, because |R| > |N|. For now, I think the idea about computability is still very unclear and abstract, and I expect to learn more about it in future courses.

Honestly, as the last week of the course, my friends and I are not as focus as previously in the class. However, we definitely have learned a lot of new things in this course with the help of professors and TAs. I must thank all of them and also my friends and classmates for the time we spent together in this course, and I wish everyone and myself can get a good score in the final exam!

(CSC165)_Nov23_Halting Problem

This week, although we had only two lectures, the content is really much harder for me to digest. Suddenly, we went from basics to a much deeper topic on halting problem and compatibility. In terms of halting problem, it is accordingly  one of the first problems to be proved undecidable by Alan Turing in 1963. 

Basically,  the problem is to determine, if a program will eventually halt when run with given input. It is clear, some specific program can have a implementable halt; however, a general halt is intuitively very hard to get, and in fact it is proved to be impossible to get. This is the interesting part of this lecture.  I was expecting an proof like we did previous in this course, but the one we saw was quit supervising to me. 

def navel_gaze(f):
    while H(f, f):
        pass
    return 42

This is a 'simple' counterexample, because it will halts if and only if it doesn't halt, which is clearly a contradiction. 

Serving as a important background information of computability, halting problem gave me a different taste on logic and math. It is difficult to come up with a proof, but when reading the proof, the idea is not all that complex.

(CSC165)_Nov15_BigOh/Omega/Theta(Week 9-10 Topic)

For these TWO weeks, we learned three major topics in evaluating the efficiency of programs, and they are Big-Oh, Big-Omega, and Big-Theta.

Based on what we can do in counting steps, we may be able to establish a specific formula for the program, and very possibly we may just get an general idea about the program. For example, it is Cn^3+K, CK^n, or Clnn (where, n is variable, C and K are constants). In these general form, the three topics helped us the categorize these programs. More specifically, Big-Oh gives us an upper bound, Big-Omega, gives us a lower bound, and Big-Theta is a tight bound, which is like a upper and lower bound.

So, more precisely, for any function f, which takes input of natural number and gives output as positive real number, we define Big-Oh, Big-Omega and Big-Theta respectively as following:

So, the questions we will possibly encounter in these topics may include prove or disprove of a given function in Big-O, Big-Omega, or Big-Theta. The basic steps of proving it:

1) pick c, and b

2) assume a generic n 

3) assume antecedent

4) connect antecedent with conclusion

5) close the assumptions

Actually making the connection between antecedent and conclusion is the most hard part of the proof. However, in general, after determining the goal, we can work on two different directions (reducing the larger element to approaching the smaller one and the other way around). In fact after going through the examples in lecture and questions in tutorial, I find there is always a relatively big space for us to approach the conclusion. Thus, there normally won't be a single right answer for these questions.

On the other hand, we disprove the statement by following the proof structure and prove the negation of the statement. I personally feel disproving is harder than proving, since it is harder to "pick" that n in accordance with assumed generic B or c. So, I should definitely work more on these kind of exercise.

(CSC165)_Nov 2_Counting_steps?

Since last week, we begin to learn counting steps. In addition to the surprise that steps are actually harder than I thought  to count, I was actually wondered why that is even relevant.

Counting steps of a simple and brief program actually can be very helpful, because we can get a exact mathematical expression to reveal the relationship between the total steps and the size of input. This can be somehow hard in math, but it turn out to be make me unintentionally begin to realize the importance of efficiency of the algorithm of a program.  Of course, at this moment, in my first year CSC programming course, I may not use a "large" amount of information or data, but in real world the potential amount of data could be huge.

Many online information about this topic show us the length of time increased as a result of different function of the 'steps'. However, the one below very impressive and it is another way to present the issue related to efficiency.

(N1 to N6 represent the size of largest problem can be solved in one hour)

	With present computer	With computer 100 times faster	With computer 1000 times faster
n	N1	100N1	1000N1
n^2	N2	10N2	31.6N2
n^3	N3	4.64N3	10N3
n^5	N4	2.5N4	3.98N4
2^n	N5	N5 + 6.64	N5 + 9.97
3^n	N6	N6 + 4.19	N6 + 6.29

(Reference: M. Garey and D. S. Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness)

We can see from the table, for programs with low efficiency, within a limited time, the problem-sovling ability won't really increase noticeably even the computer is 1000 times faster. Therefore,  the technology developing, a focus on efficiency algorithm should necessarily be highlighted, because inefficiency well significantly diminish the result from the faster hardware.