Time passed so quickly that csc165 is almost come to the end. At the beginning of the course, i thought i would not do well since i was not good at logic. And i also wonder that why we need to write blog each week. However, at this time, my thought totally changes, the blogs not only force me to follow up the lecture material but also help me to review on topics that are important in the final exam. There are some of the parts in the blogs that i want to improve. I think i can write more on my own thought about the course throughout the three months. Therefore, the blogs can keep track of my own feelings , which is what blogs usually do.
I like what Ji Yong Choi has mention about the course " I learned a lot of new information that I can use in my future studies."
(http://165choi.blogspot.ca)
CSC165 serves as a milestone of my CS journey and i really enjoy take such a course.
Good Luck everyone with the final exam and hope to see all of you in CSC236!!
Logic Station
Wednesday 3 December 2014
Induction--Week 12
This week we learn a proof technique called induction. Induction basically is used to prove something (ex: p(n) ) is true for natural number n. The idea of induction is similar to dominoes. In order to show that all the dominoes fall, we have 2 steps to do. First, we need to show that the first domino falls, and second, we assume the n-th domino fall and we can come to the result that the (n+1)th domino also falls. At first, it may be hard to understand, but students can think through the ideas of dominoes and find that the dominoes affect makes sense and it helps to understand the induction proof. I have read through some of the blogs written by the classmates and pretty agree with what they have said about the induction proof . For instance, Faye has mention the class example of how to induction work.
(http://165slog.blogspot.ca/2014/12/week-12.html)
ex: In order to prove p(n) is true for all natural number .
1. base case: p(0) is True
2.inductive step: assume p(n) is true and p(n+1) is also True
(http://165slog.blogspot.ca/2014/12/week-12.html)
ex: In order to prove p(n) is true for all natural number .
1. base case: p(0) is True
2.inductive step: assume p(n) is true and p(n+1) is also True
That is the way how we prove p(n) is True for all natural number.
Sunday 30 November 2014
Halting Problem--Week 11
This week we discuss that there are some problems in the world that can not solved by algorithms. That is there are uncomputable problems existed for any reasonable computational model. Consider the following halting problem:
def half(f,i) :
'''return True iff f(i) eventually halts''
we are told that this halt function can not to be implemented. Here is the proof:
assume halt exist.and there are such function exist below:
def confuse(f):
def halt(f,i):
#some code here
if halt(f,f):
while True:
pass
else:
return False
we first assume confuse(confuse) halts, then halt(confuse,confuse) is True, then we enter the infinite while loop.
Therefore, we assume confuse(confuse) halts , but got the result of not half
we then assume confuse(confuse) doesn't halts, then we enter the else, which return False.
once again we assume confuse(confuse) doesn't halts but it halts.
so no matter which case we consider, we got the contradiction, that is halt doesn't exist.
def half(f,i) :
'''return True iff f(i) eventually halts''
we are told that this halt function can not to be implemented. Here is the proof:
assume halt exist.and there are such function exist below:
def confuse(f):
def halt(f,i):
#some code here
if halt(f,f):
while True:
pass
else:
return False
we first assume confuse(confuse) halts, then halt(confuse,confuse) is True, then we enter the infinite while loop.
Therefore, we assume confuse(confuse) halts , but got the result of not half
we then assume confuse(confuse) doesn't halts, then we enter the else, which return False.
once again we assume confuse(confuse) doesn't halts but it halts.
so no matter which case we consider, we got the contradiction, that is halt doesn't exist.
Sunday 23 November 2014
Disprove Big-Oh ---Week 10
last week, we introduce the big-Oh prove, this week we disprove the big-Oh.
Here is one of the examples:
Disprove n^3 O(3n^2)
we first negate cR+, BN, nN, n>=B, n^3<=c(3n^2)
cR+, BN, nN, n>=B^( n^3)>c(3n^2)
proof:
assume c belongs to R+ and B belongs to N, (Generic c,B)
pick n=B+ceil(3c)+1 (then n belongs to N)
then n>=b
then n>=B
then n^3=n*n^2
then n^3>3c*n^2 (since n>3c)
then (n>=B)^ n^3>3cn^2
then cR+, BN, nN, n>=B^( n^3)>c(3n^2)
Here is one of the examples:
Disprove n^3 O(3n^2)
we first negate cR+, BN, nN, n>=B, n^3<=c(3n^2)
cR+, BN, nN, n>=B^( n^3)>c(3n^2)
proof:
assume c belongs to R+ and B belongs to N, (Generic c,B)
pick n=B+ceil(3c)+1 (then n belongs to N)
then n>=b
then n>=B
then n^3=n*n^2
then n^3>3c*n^2 (since n>3c)
then (n>=B)^ n^3>3cn^2
then cR+, BN, nN, n>=B^( n^3)>c(3n^2)
Big-oh of polynomials--Week 9
This week we introduce the big-Oh of polynomials. First, we introduce what is big-Oh O(n^2)? It is a polynomial function that take a natural number and return a positive real number such that
cR+, BN, N, n>=B, 3n^2+2n<=c(n^2). This may look hard to understand, so we can give a simple example of big-Oh proof.
Prove 3n^2+2n O(n^2)
cR+, BN, nN, n>=B, 3n^2+2n<=c(n^2)
Pick c=5 ,then CR+
pick b=0, then BN
assume nN,
assume n>=B
then 3n^2+2n<= 3n^2+2n^2
=5n^2
=cn^2
then n>=B ⇒ 3n^2+2n<=cn^2
then BN, then n>=B ⇒ 3n^2+2n<=cn^2
then cR+, BN, nN, n>=B, 3n^2+2n<=c(n^2)
cR+, BN, N, n>=B, 3n^2+2n<=c(n^2). This may look hard to understand, so we can give a simple example of big-Oh proof.
Prove 3n^2+2n O(n^2)
cR+, BN, nN, n>=B, 3n^2+2n<=c(n^2)
Pick c=5 ,then CR+
pick b=0, then BN
assume nN,
assume n>=B
then 3n^2+2n<= 3n^2+2n^2
=5n^2
=cn^2
then n>=B ⇒ 3n^2+2n<=cn^2
then BN, then n>=B ⇒ 3n^2+2n<=cn^2
then cR+, BN, nN, n>=B, 3n^2+2n<=c(n^2)
Sunday 9 November 2014
Counting Time Complexity--Week 8
This week we start to learn the interesting and harder staff-----Time Complexity.
I will give a simple linear search python function to talk about the time complexity.
ex:
def LS(A,x):
'''Return an index i such that x==L[i]. Otherwise, return -1.'''
i=0 (Line 1)
while i<len(A): (Line 2)
if A[i]==x: (Line 3)
return i (Line 4)
i=i+1 (Line 5)
return -1 (Line 6)
so, if we give an input (A=[2,4,6,8], x=4), what will the time complexity be:
we can trace our code like this:
Line 1: 1 step (i=0)
Line 2: 1 step (0<4)
Line 3: 1 step (A[0]==4)
Line 5: 1 step (i=1)
then again, we go to while loop
Line 2: 1 step (1<4)
Line 3:1 step (A[1]==4)
Line 4: 1 step ( return 1)
so our python function ends here, if we count the total time complexity, it will be 1+1+1+1+1+1+1=7 steps
We can even turn this question into a harder question: what is the worst case in which x isn't in A?
then we can think like this :
line 1 : 1 step (i=0)
while loop : 3* n (line 2,3,5 executes once for each 0 to len(A)-1 , which line 2,3,5 executes once for n times)
then we have 2 more steps to add, which is last while loop check and the last line 'return -1')
so in worst case, the time complexity is 3n+1.
I will give a simple linear search python function to talk about the time complexity.
ex:
def LS(A,x):
'''Return an index i such that x==L[i]. Otherwise, return -1.'''
i=0 (Line 1)
while i<len(A): (Line 2)
if A[i]==x: (Line 3)
return i (Line 4)
i=i+1 (Line 5)
return -1 (Line 6)
so, if we give an input (A=[2,4,6,8], x=4), what will the time complexity be:
we can trace our code like this:
Line 1: 1 step (i=0)
Line 2: 1 step (0<4)
Line 3: 1 step (A[0]==4)
Line 5: 1 step (i=1)
then again, we go to while loop
Line 2: 1 step (1<4)
Line 3:1 step (A[1]==4)
Line 4: 1 step ( return 1)
so our python function ends here, if we count the total time complexity, it will be 1+1+1+1+1+1+1=7 steps
We can even turn this question into a harder question: what is the worst case in which x isn't in A?
then we can think like this :
line 1 : 1 step (i=0)
while loop : 3* n (line 2,3,5 executes once for each 0 to len(A)-1 , which line 2,3,5 executes once for n times)
then we have 2 more steps to add, which is last while loop check and the last line 'return -1')
so in worst case, the time complexity is 3n+1.
Sunday 2 November 2014
Inference Rules-Week 7
Up to today, we have learned some rules of inference to allow us to reach conclusions about certain situations. Here are some of them:
Conjunction Elimination: if we know A^B, we can conclude A and B are both True.
Existential Elimination: if we know that there exist a belongs to X, P(a), then we can certainly pick an element with that property. Pick a' belongs to X, then p(a').
Disjunction Elimination: if we know that A V B, and we know that not(A), we can conclude that B must be True.
Implication Elimination: if we know A implies B, and we also know that A is True, we can conclude that B is also True. On the other hand, if we know not(B), we must conclude that not(A) must be True.
Universal Elimination: if we know that for all x belongs to X, P(x), then if we choose any a belongs to X, we can conclude that P(a) must be True.
Implication introduction:if we assume A and then B follows, then we can conclude that A implies B
Universal Introduction: if we assume that a is generic element of D, and we derive P(a), then we can conclude that for all a belongs to D, P(a).
Existential Introduction:if we can show that x belongs to X, P(x), then we can conclude that there exist x belongs to X, such that P(x).
Conjunction introduction:if we know that A and we know B, then we can conclude A^B
Disjunction introduction: If we know A, we can immediately conclude that A v B
Conjunction Elimination: if we know A^B, we can conclude A and B are both True.
Existential Elimination: if we know that there exist a belongs to X, P(a), then we can certainly pick an element with that property. Pick a' belongs to X, then p(a').
Disjunction Elimination: if we know that A V B, and we know that not(A), we can conclude that B must be True.
Implication Elimination: if we know A implies B, and we also know that A is True, we can conclude that B is also True. On the other hand, if we know not(B), we must conclude that not(A) must be True.
Universal Elimination: if we know that for all x belongs to X, P(x), then if we choose any a belongs to X, we can conclude that P(a) must be True.
Implication introduction:if we assume A and then B follows, then we can conclude that A implies B
Universal Introduction: if we assume that a is generic element of D, and we derive P(a), then we can conclude that for all a belongs to D, P(a).
Existential Introduction:if we can show that x belongs to X, P(x), then we can conclude that there exist x belongs to X, such that P(x).
Conjunction introduction:if we know that A and we know B, then we can conclude A^B
Disjunction introduction: If we know A, we can immediately conclude that A v B
Subscribe to:
Posts (Atom)