Final Update

This is probably the last post in the slog. In this csc236 course slog I wrote 20 posts, average 1.5 post per week, including a problem solving question. Most of the posts are the thought about the course material. Unlike other classmates who gonna post mass posts right before due date, I keep writing slog in every single week. As I mentioned before in the 165 course slog, I think slog is a very good environment for us to review course material and share the thoughts. If anyone post large amount at one time, probability the posts will copied from somewhere else or just some crap words that make nonsense. So I keep writing post every single week. Need to mention that in the 165 slog I got A for my slog, I believe this csc236 slog will Aces as well.

I keep this slog default layout, white background and black fonts. Sometime when I get into others slog, someone try to make the background black or put really shinny color, honestly, I won't read those slog for more than 1 or 2 posts, coz, it is really not read friendly. So, I keep my slog simple and default the layout and color.

Tomorrow we will have a test and there is only a final left. I really appreciate Danny's effectively teaching for this course. My friends told me this course is really hard, I just want to say Danny really make this course easy for us to understand. Thank you Danny. I hope you can teach us for any other course later on.

OK, probability this is all I want to say for this slog. Thanks anyone that review and comment my slog.


Simon
Dec. 2008

PSA

The second topic today is about PSA, a updated version of FSA, that we are allowed to use a stack. This is the perfect case that we can use this stacked automate to solve some problems like Matching Parentheses or like the one we left after lecture, same number ones and zeros. I didn't get a chance to think this question deeply before I wrote this slog. I think I have some sort of clue that when we see a 0, we push 0 to the stack, when we see a 1, we pop a 0.

we need to have a start states and two states that paralleled to each other that accepting 1:/epsilon X and 0:/epsilon X respectively. Furthermore, we need to have another states that connecting with the two states mentioned above, realize that I should label them as S1 and S0, then they connected to the states S3 say... to be continued...

CFG to FSA

Coming later today's lecture, coz I had a math test before that. Fell weird that danny use the blackboard again. Today's lecture is about converting CFG to FSA. Topic is interesting, coz there are connection about the regular expression and FSA that we learned weeks ago. Again, now we are talking about the connection of CFG and FSA, which is more related each other than RE to FSA, personally speaking.

The method is straight forward, instead of having a long states and all the lines, we put each line from one state to another as an single context free grammar. There is works. Just remember that we need to have a right linear that some state to empty or any string preappend to a the terminal state.

Problem Solving Question.

Piles of pennies

You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:

L: If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.
R: If the right pile has an even number of pannies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

What about arranging things so that one of the piles has other numbers in the range [0,64]? What about starting with a different number of pennies in the left drawer?

****************************************

Step 1: Understand the problem.
This question need us to figure out the way to rearrange the pennies in the two sets by only apply two operations namely, L and R. The operation of L and R are identically the same, only difference is they only implement the operation in each specific set.

Some observation as follow:
(0). The initial states requires the left basket only can contain even number of pennies, otherwise there will be no operation for the problem.
(1). We can only use the L or R operation if any set contains even number of pennies. Otherwise the L or R and be implemented.
(2). If one of the set contains odd number of pennies, we can't have further operation until we move odd number of pennies into this set from the other one.
(3). Following the last step, if odd number of pennies moved in, then other set moved from will end up with odd pennies. This means we can't have any further operation for moving from set .

Step 2: Devising a plan.
(1). Observe the first few cases to see if any pattern can be concluded for this problem.
(2). Try to give a formula to instruction about the operation rules.
(3). Try to generalize the case with different start case.

Step 3: Carry out the plan.

Q1: left drawer contains 64 pennies, end with one of the drawers has 48 pennies
(0). 64|0 # initial case
(1). 32|32 # move half(32) from left to right
(2). 48|16 # move half(16) from right to left
Then at the end of the two operations we end up with 48 pennies in one of the drawers as required.

Q2: one of the piles has other numbers in the range [0,64]
(0). We can easily see that we can't generate a none penny pile in our system. Since zero times two is still zero, that's means we can't divided a pile by half inorder to generate a zero.
(1). Since we can't generate zero, how about 1? The answer is yes, since in this algorithm 64 is a power of 2 number, the only thing we need to do is to divided the same pile by many times. then we can easy to get a 2, and then once again, we can get 1.
(2). Actually we can generate any number by provide the initial value of 64 or any powered 2 natural numbers. The proof can be done by using recursive loop.

Q3: What about starting with a different number of pennies in the left drawer?
(0). As mentioned above the left drawer can't start at a odd number, otherwise there will be no more operation.
(1). Any number that powered by 2 is a good starting number, this means we can generate any number other then 0.

Step 4: Looking back.
This question is an open question, there can be a lot of questions related to this question, by simply change the starting value in the left drawer or by give an different operation rules.

S->S means empty

In this weeks lecture danny talked about the context free grammars. 

When danny ask a question about what the grammar S->S, stands for?

My first instinct is if s always return s itself, then s can't be anything that related to repetition which we are frequently used in the regular express, we called it Kleene star. Since Kleene star is out of the consideration, i made a conclusion that S->S represent a finite string.

However, danny said it represent empty. 

I think about it after class, found danny is right.

Here is the thing, since we start at S, and our destination is always S, the trick is S is start point and also a destination point. Thus, that's means you always stay at where you are. Thus, the S->S means empty. 

It may sounds confused by how about S is /epsilon (empty string), actually, in the lecture for FSA, we use /epsilon  to direct start state to another states, if S->S is /epsilon then is contradict with S->S where the destination state S is itself, it doesn't direct to any state other than itself. Thus S->S only should be empty.

Another way to think about this question is there is no other output, i.e. S-> B. Thus if any CFG that doesn't include a end point other than itself, this CFG either never ends or just empty. 

S->S means empty

Pumping Lemma

Found an interesting article about pumping lemma, it is a poetry about pumping lemma. Here it is.

The Pumping Lemma, in poetic form

“Any regular language L has a magic number p

And any long-enough word in L has the following property:

Amongst its first p symbols is a segment you can find

Whose repetition or omission leaves x amongst its kind.”

“So if you find a language L which fails this acid test,

And some long word you pump becomes distinct from all the rest,

By contradiction you have shown that language L is not

A regular guy, resiliant to the damage you have wrought.”

“But if, upon the other hand,x stays within its L ,

Then either L is regular, or else you chose not well.

For w is xyz, and cannot be null,

And y must come before p symbols have been read in full.”

“As mathematical postscript, an addendum to the wise:

The basic proof we outlined here does certainly generalize.

So there is a pumping lemma for all languages context-free,

Although we do not have the same for those that are r.e.”

By Martin Cohn and Harry Mairson

Regular Expression

Many of us have written applications where we have used regular expression for different tasks, like validation , parsing and other related task. Like the a1 of 207, we have the regular expression to read the user's input of next move. After learn regular expression in csc236 i can understand how those code works. Regular Experssion is quite a powerful tool, and has been available in most of the programming languages. I believe, most of the time, like us, use this tool is to search specific words in a long paragraph.

In csc236, seems we talk about the regular expression, we only focus on binary string which contains only 0 and 1. The more interesting about regular expression is to deal with words that other than bianry string. Like the pattern contains words and numbers, or even the charater witht the back slash.

Usually in a regular expression ‘\’ is used as a the escape sequence , to escape meta characters. Regular Expression also support a construct called ‘character classes’ ,which can be roughly taken as a set of characters. There are some pre-defined character classes like \d \w \s etc. and if you need a more customized version you can define your own using Square brackets notation "[]" with represent a set that match the pattern inside.

The world inside the square brackets is much different than the one outside.  Inside the brackets , there are only two meta characters, ‘^’ and ‘-’; even an opening bracket ‘[', asterisk '*' , plus sign '+' are not considered as meta inside []. Furthermore , [] has no escape sequence within them. Now what you will do if you want to have ‘^’ , ‘-’  and ‘]’ inside a character class.

Even Zeros and Odd Ones

This question left in today's lecture is interesting, said need to find a regular expression by using the set (0,1) to produce even zeros and odd ones. The graph which is drawn in the lectur can slove this question easy. Image there is four staes say s0, top left, s1, top right, s2, bottom left, s3 bottom right. Obvious we know that:
s0 and s1 represent even ones, while s2 and s3 represents odd ones.
s0 and s2 represent even zeros, while s1 and s3 represents odd zeros.
Here our question becomes the way that travesal from s0 to s2 where is our destination that represented by even zeros and odd ones.
After all the setup above, we can start our travesal. One thing need to point out is there are many self-circle(?what is the official name for this?) should be considered, like s0 to s1 then back to s0.
Ok, here we go. Start from s0.
1. We can directly go from s0 to s2 where is our destination, done! Easy case, may called base case??
2. From s0 to s1 to s3 to s2, which is the clcokwise traversal. Thus we can get the expression like 010. However, we can have s0 to s2, not stop here, but go to s3 and then back to s2. There are many cases need to consider, keep in mind that s3 can go back and forth with s1 and s2 many times. Likely wise, we can have a countclockwise traversal, from s0 to s2, it is a duplicate expression from where we discussed above. Thus we can conclude that 1+(01+10)(11+00)*0 is our expression.
3. The above expression just from s0 to s2, we know that there are a lot of ways from s0 to anywhere states and come back to s0 again, this situation should concatenate with the expression above. From s0 to s1 back to s0 will gives us 00, so to s2 back to s1 will gives us 11. More states now s0 to s1 to s3 back to s1 will give us (01+10)(00+11)*(10+01), so or then up and concatenate with first expression gives us.
(00+11+(01+10)(00+11)*(10+01))*(1+(01+10)(11+00)*+0)

Non-equivalent Ternary Tree.

After several weeks' study on induction prove. I gotta a better sense about the ternary tree question than I was first time doing assignment 1. This question is interesting now. I checked some books about the property of trees. I kinda found a closed form formula for this question. which is 3n!/(2n!n!(2n+1)). However, It is kinda not that easy to prove. My way to solve this problem is using Sigma for different trees and get the product of them. It is sound silly comparing to that perfectly closed form formula, but it is easy to proof, and understand. 

Assignment 1 Remark??

I have talked to Danny after term test 1. I am told to send him an email for remark. I did so. However, I did not seen any update from online marking tool or an email back from Danny. Did you received my email? or else?

Term Test 1

This test is fairly easy, just spent 30 minutes to finish it. But still i did not get a perfect mark. The problem is the question 1. The one that require us to prove for n>5, P(n). I use complete induction here. I know I am gonna use all the cases for 0 to n-1. However, maybe I think it is too easy to dig it deep. The base case in my proof is not adequate. Since I will use P(n-2) thus, I have to show the base case for n=8, since n-2=6 this is where the proof should start. My base case is simple P(6), P(7) without P(8). Two marks are taken away, because of the base case problem.

Many time, When I am doing an induction prove question, i am focus on how to show P(n) to P(n+1) without pay much attention on the base case. (In most case, it is too obvious to say any words) However, like the question 1 in the term test, the base case is actually the key for this proof, maybe the only tricky in this question. So, next time, when i am dealing with induction proof, i should take care base case carefully, coz tricks born there.

Busy

I am so busy recently, we have a lots of assignments due last friday, and before that we have 236 term test 1. This week, yesterday, we just finished a statistic test. So there is a lot of missing updates for csc236.

DIY Closed Form

I am a little bit confused about the question in class. H(n) is defined as 

H(n)=0 for n=0

H(n)=2 for n=1

H(n)= 3H(n-1)-2H(n-2) for n>1

I can understand the alpha and beta manipulation staff, but how to get the h0=1, h1=2 and the formula h^2=3h-2? Why it is as this?

What I did for this question is to list down for n from 0 to 6, we can quickly found the patten that H(n) = 2^(n+1)-2, since every H(n) is the power of n+1 and less than 2. But how to get h0 and h1 and what are those symbols stand for?

A1 Schema

Just checked my a1 mark online, it is really bad. I am question about the marking schema? Why my solution only get 2 out of 5. And the reason is just some gaps in proof. Wondering how detail it should be when we are writting our assignment. Why it is keep saying we have gaps in our proof? We did everything correct but only get half mark?? I am very dispointed about the result. Feel a little down about this course, if the TA keep try to mark assignment or any test like this way. By the way, for the question two, Danny replied my slog said my ways may be a good one, but the TA just stick to the way on the sample solution, give me 2 of 5 on this one. And wondering any way to remark on this assignment?

May possible to check my work at g8simon.

Prep Term Test 1

Term Test 1 is settled on the next Friday. I think the main topic on this tt1 is induction prove.

Assignment 1

The assignment 1 sample solution is posted yesterday. I read through this solution today, and the question 1 is almost the same as my solution. It could solved by adding one extra triangle.

The question 2 is slight different from my work, despite, we all divide the n+1_meal menus to the one include n+1_meal(s1) and the one not include n+1_meal.(s2) We know that the n+1_meal that not include the newly n+1_meal partition is identically the same as n_meal. My way does not inverse the s2 menu, instead I just jump back and forth from s1 to s2, which draw in graph is like a 0-1 voltage diagram. Which we has s1[0] to s2[0] to s2[1] to s1[1] to s1[2] to s2[2] to... and so on. I found my work is working but kinda not concise as the solution which is simple inverse the s2 and rest of work is just concatenate the head and tail. I will see whether my work will get full mark or not when the marked paper handed back.

The question 3 is interesting. Actually I have no idea about this question at all when I first read it. The I read some info. like wiki and other websites that have explanation of this kind question. After I grab all the key concept, I write my own work on this question, but it turns out, it is similarly to the one posted as solution. Maybe this is the standard solution or way to solve this kinda question? For the square root of 5 part, I use the same patten as the question to prove square root of 2 is irrational, simply because I can handle that proof well. So I just slight change and parameters, and leave the rest of answer as similar as proving square root of 2 question.

PWO PCI PSI

For the first two weeks, we have done a lot on those Principles( Well-ordering, simple-induction and complete induction). Today's lecture we actually made those principles more clearly about their relationships. Those terms are essentially all the same. One term can be drived from the others. Those proofs are we have done today, is written in textbook as well, so I don't want to repeat here. It is well worthy to read through, an it will make all those concepts are more clearly. 

Full Binary Tree

The full binary tree question is really about the recursive theorem that we have practiced a lot in the course CSC148. Question is quite simple to answer. 

By using the complete induction, we first need to assume all the node n full binary trees have odd nubmer nodes. Since every internal node of a full binary tree have two nodes. We called them Left and Right respectively. 

Futhermore, as we assumed, the number of node for Left and Right is also odd for both of them. Thus, the total nodes for the full binary tree is simple, 1+L+R, where L and R are number of node for Left and Right subtree respectively. 

As we can see. the 1+L+R = 1+(L+R), since L+R is a even number. Then 1+L+R must be a odd number. Then we end the discussion for this full binary tree question. 

Actually before this lecture, I never think about the connection between recursion and complete induction. I think the more knowledge we got, the more connection we can find. All different course and material are actually connected each other.

Complete Induction

Today we have studied complete induction. Since it still part of induction approach, most of the theories are the same. However, instead of show P(n+1) from assumption of P(n), we need a stronger assumption which means we need to hpy. all the cases before the number n are correct/hold, then we need to show P(n) hold.

A simple way to know a induction is simple or complete is to see if we acturlly need mention P(n+1). Part of this because, I am not sure true or not, there is no need to show P(n+1) hold for complete.

The case we have seen in lecture is a great example to get understand the complete induction. First, there is no easy to induct from P(n) to P(n+1). Second, we need more prerequisite we need in order to induct P(n), which means we need P(n-1), P(n) all down to the lowest cases.

The full tree case is interest. I will discuss it afterwards.

All About Setup

I got my slog setup in Blogger. Last year we use UofT Slog system, however, this year, I checked some students already post their slogs. Surprisely, they all use Blogger. So, I am gonna jump in as well. As you can see this is my first slog for CSC236, really not much course content. I might add up course material later on. Ok, enough for the first slog post.