It's all about csc236 in UT

Episode of Proving the regular expression denotes a language.

2008-12-05T13:36:00.000-08:00

Question. Consider the language L, consisting of strings over the alphabet /sigma = {0,1}; that have an even number of 1s. For each of the regular expressions below, either prove they denote L, or else nd a counter-example that shows they do not. Your counter-example should either exhibit a string that is inL but not denoted by the regular expression, or else one denoted by the regular expression that is not in L.

To give out a counter example is easy, so here I will not show that part.

(b) R2 = (0 + (10*1))*
R_2 does denote L.

UNDERSTANDING THE PROBLEM
To prove a regular expression denotes a language, we need to show that
R2 is a subset of L and L is a subset of R2. Here we can use structural
induction.

DEVISING A PLAN
1) Prove that R2 is a subset of L
2) Prove that L is a subset of R2

CARRYING OUT THE PLAN
Let L be the set of binary strings that have even number of 1s.
Then the regular expression R_2 = (0 + (10*1))* denotes L.
Claim: for any string x, x is in L if and only if x is in L(R_2)
1)
Proof.[IF] Let x be an arbitrary string in language L,
then x contains even number of 1s, say 2n for some natural number n.
Then x can be decomposed as the concatenation of X_1 through X_k
where X_i (1 <= i <= k) = substring with even number of 1s.
To have even 1s, and for small unit, X_i has either zero 1 or two 1s.
Then x can be formed as below:
x = (0 + (1(0...0)1))(0 + (1(0...0)1))......(0 + (1(0...0)1))
X_1 X_1 X_k
There might me one or more zeros between two 1s, thus we use (10*1)
to denote the substring with two 1s.
Then each X_i is in the language (0 + (10*1)), 1 <= i <= k.
So x is in the language L((0 + (10*1))^k) which is a subset of
L((0 + (10*1))*). Thus language L is a subset of L((0 + (10*1))*).

2)
[ONLY IF] Let x be an arbitrary string in L((0 + (10*1))*).
Then there is some natural number k, and y_0, y_1, ..., y_k in /sigma *
such that y_i is in L(0 + (10*1)), for all i such that 0 <= i <= k.
Therefore there are natural numbers m_1, m_2,...,m_k such that
y_i = 0 + 1(0^(m_i))1, for all i such that 0 <= i <= k.
Obviously, y_i is either 0 or 1(0^(m_i))1,
So y_i either has no 1 or two 1s.
Let a,b be two natural numbers where a + b = (k - 0 ) + 1 = k + 1.
Assume there are "a" substrings y_i that is 0, and "b" substrings
y_i that has two 1s. Then the total number of 1s is
0*a + 2*b = 2b, which is even. Thus x is in language L, as wanted.

Since every string in L(R_2) is in language L, and every string in
L is in L(R_2), R_2 denotes L.

Look Back
This episode can be used to prove most of the questions about
proving the regular expression R denotes L.

Problem Episode on proving the program is correct

2008-12-05T13:16:00.000-08:00

Question.
Prove that if quotRem(n,m) is called with arguments that satisfy the precondition, it terminates, and
when it does it satises the postcondition.
def quotRem(n,m) :
# Precondition: n,m are natural numbers
# m is not 0
r = n
q = 0
while (not (m > r)) :
r = r - m
q = q + 1
# Postcondition: n = qm + r and 0 <= r < m
return [q, r]

UNDERSTANDING THE PROBLEM
Given a program with a while loop. We need to prove that the program
acturally terninates and the precondition implies the postcondition.
For each while loop, r decreases by m, and q increment by 1. Since the
loop condition is on r, which is a decreasing natural number, thus the
while loop will terninate. We will show the correctness of the program by
proving using induction.

DEVISING A PLAN
1) Prove that for each loop, the loop invariant is correct.
2) Prove the while loop acturally terminates.
This proof need 2 steps: 1st is to prove that the loop invariant is in a strictly
decreasing sequence. Then by PWO , we show that the loop terminates.
3) Prove that the precondition implies the postcondition. This step is simple,
since we have shown most of the needed condition in 1) and 2).

CARRYING OUT THE PLAN
1)
Let P(i) be if there is i iterations, if the precondition is true,
then n = q_i * m + r_i and 0 <= r_i < m is a natural number.
Claim 1a: for all natural number i, P(i).
Proof.
Base case: If i = 0, then r_0 = n by line 1 and q_0 = 0 by line 2.
So n = 0 + n = q_0 + r_0. Since the loop does not execute,(0 iteration)
it's obvious that the condition (not m > r) fails,
so m is greater than r_0. Since r_0 = n is a natural number by precondition,
r_0 >= 0. So we have 0 <= r_0 < m. So P(0) is true.

Induction step: Assume that P(i) is true for any natural number i.
We need to show that P(i+1) is true.
If there is no (i+1)th iteration of the loop, P(i) is vacuously true.
Otherwise, assume there is (i+1)th iteration and precondition holds.
r_(i+1) = r_i - m by line 4, q_(i+1) = q_i + 1.
n = q_i * m + r_i (by IH) = q_i * m + r_i + m - m
= m *(q_i + 1) + (r_i - m)
= m * (q_(i+1)) + r_(i+1)
Hence P(i+1) is true.

We have shown that P(i) implies P(i+1) for any natural number i,
So we have P(i) for any natural number i.

2)
Claim 1b: Let E_i = r_i - m be a natural number. If m <= n,
m is a positive natural number, then E_i is a strictly decreasing sequence.
Proof: Base case: if m = n, then E_0 = n - m = 0. E_1 = r_1 - m = 0 - m < 0.
E_1 is not a natural number, so the set E_i only contains 0, we can
say that this is a strictly decreasing sequence.

Induction step: if m < n, and there is (i+1) iterations,
then r_(i+1) = r_i - m. We have
E_(i+1) = r_(i+1) - m = (r_i - m) - m = r_i - 2m.
By precondition, we know that m is not equal to 0 and m is a natural number.
So m > 0, and r_i - 2m < r_i - m, which implies E_(i+1) < E_i. Thus E is a
strictly decreasing sequence.

Hence E_i is a strictly decreasing sequence.

Claim 1c: quotRem(n,m) terminates.
Proof: n,m are natural numbers. If m > n, then we are done since the loop will
not execute and so will terminate. Otherwise, m <= n, the the loop will execute.
We have shown that natural number E_i = r_i - m is a strictly decreasing sequance
and non-empty since it contains at least E_0 = r_i - m = n - m >= 0.
Then by Principle of Well Ordering, there is a least value, say E_k, which must
also be last (strictly decreasing), which means there is no (k + 1)th iteration
of the loop. Thus the loop terminates.

3)
Claim 1d: If precondition is true, then the postcondition is true.
Proof. We have shown that the precondition implies that the loop terminates and
for each loop n = q_i * m + r_i and 0 <= r_i < m.
Thus for the last loop n = q_k * m + r_k and 0 <= r_i < m, and the loop
terminates. Write this form without indicating the subscript, we have
n = q*m + r and 0 <= r < m, satisfying the postcondition.
Therefore, the precondition implies the postcondition.

Looking Back
This episode can be used to prove most of the question on correctness of the program.

Problem Episode on tenary tree

2008-12-05T12:57:00.000-08:00

Dene the set of ternary trees, T3, as:
(a) The empty tree, /\, is an element of T3.
(b) If trees TL; TM; TR are elements of T3 having no nodes in common, and R is a node that is not in
TL; TM or TR, then T = (R; TL; TM; TR) is an element of T3. We call TL the left subtree, TM the
middle subtree, and TR the right subtree, of T.
Consider two trees equivalent if (a) they are both /\ (the empty tree), or (b) they have equivalent left
subtrees, equivalent middle subtrees, and equivalent right subtrees. So there is one ternary tree with
zero nodes: /\, and one ternary tree with one node: (R;/\;/\; /\). For arbitrary natural number n, nd
a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Prove your
formula is correct.
Artist's impression of the three non-equivalent ternary trees with two nodes.

1.UNDERSTANDING THE PROBLEM
Given the definition of a tenary tree with 3 nodes. We need to generize a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Then we need to prove it.

2.DEVISING A PLAN
1, Analyze the tenary tree by trying some small number of nodes.
2, Generate a formula for the number of nodes of the tenary tree.
3, Prove the formula is correct by induction.

CARRYING OUT THE PLAN
1)Analysis:
Notice that if we separately analyzes the ways a tree displayed with n nodes,
we can show it as a sum of all possible ways.
Let's take 3 nodes for example. let the possible ways be G(n)
Then, case1, if the left subtree has 0 nodes
case 1a, if the middle subtree has 0 nodes,
the right subtree has 2 nodes. G(n) = G(0)*G(0)*G(2)
case 1b, if the middle subtree has 1 nodes,
the right subtree has 1 nodes. G(n) = G(0)*G(1)*G(1)
case 1c, if the middle subtree has 2 nodes,
the right subtree has 0 nodes. G(n) = G(0)*G(2)*G(0)

Symmetrically, case2 will be when left subtree has 1 nodes and case3 will be
when left subtree has 2 nodes.

Then the total way of displaying is
G(n) = G(0)*G(0)*G(2) + G(0)*G(1)*G(1) + G(0)*G(2)*G(0) + G(1)*G(0)*G(1) +
G(1)*G(1)*G(0) + G(2)*G(0)*G(0) = 3 + 1 + 3 + 1 + 1 + 3 = 12

2) So, the close form
G(n) = 1, if n < i="0}^(n-1)" j="0}^(n-1-i)">= 2

3)
let P(n) be "There are G(n) non-equivalent ternary trees with n nodes."

claim: for all natural number n , P(n)

Proof.

Base case: if n = 0, then there is only one way to display the ternary tree.
Hence P(0) is true.
if n = 1, then there is still one way to display the ternary tree by
putting this nodes on the root. Hence P(1) is also true.

Induction step: Assume for any arbitrary natural number n,
P(2),P(3),...,P(n-1) are true. We need to prove that P(n) is true.
case 1. if n <>= 2, then by Induction Hypothesis, G(i), G(j), and G(n-1-i-j)
are all true, 0 <= i <= n-1, 0 <= j <= n-1-i. Notice that if we separately analyzes the ways a tree displayed with n nodes, we can show it as a sum of all possible ways. When there are n-1 nodes, we assume n-1 cases where the left subtree contains {0,1,...,n-2} nodes(exclude root). Then for each of these case, we analyze how many ways a tree can be displayed when the middle subtree contains {0,1,..,n-2}nodes. In specific, we determine, when there are i nodes in left subtree and j nodes in middle subtree, how many ways the ternary tree can be displayed. Notice that when there are i nodes in left subtree, there are maximum (n-1)-i-1(exclude root) nodes in middle subtree and the right subtree will have (n-1)-1-i-j nodes. We know when calculating possible ways, we multiply each possible case together. In this situation, G((n-1)') = G(i)*G(j)*G((n-1)-1-i-j). We add all possible G(n')s and we get G(n-1) = \sum_{i=0}^(n-2) (\sum_{j=0}^((n-1)-i-1) G(i)*G(j)*G((n-1)-1-i-j) ). Now, we assume there are n nodes, Then, similar to G(n-1), there will be n cases, where the left subtree has {0,1,...,n-1} nodes. and the middle subtree may contains {0,1,..,n-1}nodes. when left subtree has i nodes, the middle subtree will maximum has n-1-i nodes and the right subtree will have n-1-i-j nodes. We have each little case with G(n') = G(i)*G(j)*G(n-1-i-j) We add all possible G(n')s and we get G(n) = \sum_{i=0}^(n-1) (\sum_{j=0}^(n-1-i) G(i)*G(j)*G(n-1-j)) Hence P(n) is true. We have shown that for any natural number n >= 2,
P(n-1) implies P(n).
Thus, for any natural number n >= 2, P(n).
Consider both cases, we now have shown that P(n), for any natrual number n.

4, Looking Back
Usually we can use this episode to generate the number of nodes on a tree with n children.
Even though it is somehow complecate than a simple induction proof.

conclude csc236

2008-12-04T22:39:00.000-08:00

csc236 is a good course that improves our ability of proving and thinking.
It has a fair mark destributing and overall average work load.
The lecture is very useful compare to other courses.
Also, I guess doing assignment with partners would be a good option,
but I didn't do so. I feel interacted on the lecture and more excitingly,
the professor can remember our names.
Even though I hadn't met TAs yet since I didn't go to office hours,
I believe they will be very helpful.

Overall, this is a course that's worth taking.

Test 3

2008-12-04T22:31:00.001-08:00

This test is the one that I don't really know what's going to be on it~ since we didn't have assignment on it and also the problem set is for last week. Structural induction sometimes
seems do not work.
For example, if L(R(ab*)) is the language only contains the string "a" is in L and "abb" is in
L, but the concatenation aabb is not in L which contradicts the assumption. Am I mistaken
anywhere....? I guess so and I will figure it out before the final hopefully.

Also, I'm suspitious that the pumping lemma does not imply sometimes. I didn't come out
a specific example yet, but it has so many conditions on it so that it works.

The final is comming and I hope I have enough time for reviewing.

near the end of the semester

2008-11-29T02:14:00.000-08:00

There are something new for the proof strategy, which is structural proof.
We have proved several statements about binary string with certain properties.
At first I was not comfortable with the idea of binary string and now I find
it easier and it has create a new world for proofs.
Assignment 3 is done and there is only one test left until the final.
This semester is going really fast. However I had a good time with lectures
and fair marking. I would love to take this course even if it's not the program
requirement. I hope we can have some practice test or past tests for the final
to decrease the stress of having 3finals consecutively.

Hope all of us will do fine.

we have to learn self study....

2008-11-21T20:36:00.000-08:00

I feel strongly that even though we are learning the same knowledge about regular expression in both courses csc207 and csc236, I understand better on csc236 than on csc207.
Hence, I believe instructors and the strategy for teaching matter a lot when it comes to learning new knowledge. As I go from elementary school, middle school, high school and now university, I feel that we have more abilities to learn, but the instructor has less strategies to teach.

Though I don't prefer this situation, I have to admit that this process is necessary to make people learn to self study. No one will teach you forever. It's yourself who learns the knowledge.
CSC236 is one of the course that I can mostly understand during the lecture.
So I recommend this course to all the CS students.....(though it's a program requirment)

Term Test2 is done

2008-11-09T14:09:00.000-08:00

We just had term test 2 and it's not hard.
I found that the past test helps for the question
of termination of loops.
I just need to study the lecture notes and
assignments to prepare for the test.

The test content and assignment content is fit
to what we have learned.
I have another course MAT237 which the assignment
and the test is mostly out of range.
Also, the lecture is hard to understand, so is the textbook!

I feel the course CSC236 is a good course since
I can understand on the lecture and prepare well
for the tests. It's very straight forward and clear.

If all courses are like CSC236, the university would be
much funnier.

Invariant...

2008-10-31T23:05:00.000-07:00

I kind of find it hard to find the loop invariant.
It's not very clear that what are the algorithms
to find the loop invariant.
Also, how to prove the correctness of loops
seems more difficult than the recursion....
Nested loop is even worse......
I hope I can figure it out by next week and
I hope I can do well on Test 2!~

Assignment2 done!

2008-10-28T21:42:00.001-07:00

Fortunately, I have figured out most of assignment 2.
I found that "if you were frustrated yesterday, it doesn't mean
there is no hope everafter".
5 minuts ago, it was a bit trouble, and now it becomes all clear.

People need think. In this way, they can realize how much they
actually know. Or people will never know they can do such
things...

Though the road is full of challenges, we can go through it if
we believe we can..

Assignment 2....headache

2008-10-23T13:50:00.000-07:00

I just started assignment 2 and I feel that it's alot harder than the first one.

The first question, I feel that we have met the hardest question about a tree.
I have a little bit insight about small part of the formula,
but I still feel headache about drawing trees.

The second was easy to unwind the expression. However the closed form is
not easy. I'm not sure whether we should let it smaller than certain number
or let it equal to an expression. Also, the constant ting annoys me.

I didn't start reviewing the next 2 quesion but I hope they will be easier.

after the first test

2008-10-10T08:49:00.000-07:00

I have just wrote the first midterm test and
I found it easy since it's all about induction.

The first time I new the technique of proving using induction,
I thought it doesn't make sense, because we can have many flaws.
However now, I feel that for some specific proofs, induction is great!

For one of the question in the test,
I am wondering if we need a lemma....

anyway~ hope this one is the worst, and hope I can do better and better. ^ ^

on the lecture

2008-09-30T21:49:00.000-07:00

I like better the lectures that has more frequency and less time.
because I know it's more benifitial for remembering.

In the lecture, we always hand in a paper with the pop question.
It's interesting because when I do a problem in my dorm,
I can do the question correct but in the lecture with time limit,
it seems more difficult.
I like the pop question since it makes you practise thinking
within a short time.

Problem sets

2008-09-30T21:46:00.001-07:00

Problem sets are all about lecture knowledge.

If you get all of the idea in the lecture,
the problem set will be very easy for you.

When you get stuck, go to the discussion board
and check the lecture notes. It's very helpful!

why PROOF

2008-09-29T20:36:00.000-07:00

Why do we need to prove that things are true?

when we have a very very simple and obvious hypothesis, such as 1+1 = 2, why we need to prove it?

CSC236 in my opinion

2008-09-29T20:21:00.000-07:00

Before I actually having a class of CSC236,
I thought this is a computer science course.
However, after I actually attend it, I found it's like a math course.
And now I realize that computer never goes alone without math!

I took MAT102 in UTM(equivalent to CSC165 in st George),
and I found CSC236 is totally built upon that course.
Induction proofs have dominated my first month classes
and I feel comfortable about it.
Principle of Well ordering is kind of new to me,
and I feel like PWO is a symbol of "contradiction".

Today we leaned recursion of function,
which is very similar to induction.
However, I really don't know why should we
learn all these proof strategies in order to
be a programmer.......

thought about computer sicence

2008-09-25T12:32:00.000-07:00

I don't want to complain about my assignment 1 right now.
I just want to calm down and write some thoughts about
computer science

I enrolled late for this course because I had a great summer vacation :)
and a hard time deciding if to continue the study of computer science.

Why should I learn computer science?
I asked myself, and I got some basic answers:
1, I chose it because I initially thought this course is about making games and animations:(
2, I am good at science but not arts:)
3, I can have a job right after graduation or even before graduation with high salary:)
4, computer technology is crutial in today's society:)
5, I have already taken so many courses in CS... :(
6, my mom wants me to study computer because she found it important :
7, make people more logical and professional:
8, This program make me strong in facing pressure.

Why shouldn't I?
1, As a girl, sleeping late, always siting still and facing the radiation of the computer
my skin goes wrong and my neck is uncomfortable.
2, I'd like to be outgoing and be active in the society (may be not a reason)
3, I don't want to be a computer scientist

But anyway, I have now decided to complete this hard job.
SO no more thinking and just work hard to build my knowledge in this area.