Last Day of Class

Finally! We reach the end of semester.
During this course, I leaned a lot knowledge of application of logic and proof techniques to computer science. Also mathematical inductions, correctness proofs for iterative and recursive algorithms, recurrence equations and their solutions, such as using The Master Theorem, and introduction to automata and formal language.
Wish everyone gets a great grade on final exam and I will continue working hard for final exam which is weighted for 35% of the course. Pretty high, right? =p.

And merry christmas to all!

First question in assignment3

I spent more time on the first question than the other three. I came up with no ideas at the beginning, and I logged in to piazza to seek some hints. And I found that the professor introduced a way of thinking for us to prove contradiction. Then I followed the track and came up with my solution as following. I may not get it perfectly correct. This is just what I believe one way to solve it.

The question is as following:

Let L = {x belongs to {0,1}* | fourth last bit in x is 0}. Prove that any DFSA that accepts L has at least 16 states.

And my proof is:

Claim: Let L = {x ∈ {0, 1}* | forth-last symbol in x is 0}. Any DFSA that accepts L has at least 16 states.

Proof: We use proof by contradiction to prove the above claim on L.Assume there is a DFSA accepts L has less than 16 states. Since there are 16 different combinations of the last four bits of the string, in other words , then at least two of the 16 states can be reduced to one. Let x and y be two different arbitrary states from the 16 states. We must show that this leads to a contradiction. There are four cases.

Case 1: The fourth last symbol in x and y are different.
In this case, one of the two states should be accepted by the DFSA and
the other one should be rejected. Then they cannot be reduced to the same state.

Case 2: The third last symbol in x and y are different.
In this case, if we append k ∈ {0,1} to both x and y, then the third last symbol now becomes the forth last. Because the third last symbol in x and y are different, then the fourth last symbol after appending k of x and y are different. Then, one of them should be accepted by the DFSA while the other one should be rejected. Then they cannot be reduced to the same state.

Case 3: The second last symbol in x and y are different.
In this case, if we append k ∈ {0,1}2 in both x and y, then the second last symbol now becomes the forth last. Because the second last symbol in x and y are different, then the fourth last symbol after appending k are different. Then, one of them should be accepted by DFSA, and one should be rejected. Then they cannot be reduced to the same state.

Case 4: The last symbol in x and y are different.
In this case, if we append k ∈ {0,1}3 in both x and y, then the last
symbol now becomes the forth last. Because the last symbol in x and y are different, then the fourth last symbol after appending k are different. Then, one of them should be accepted by DFSA, and one should be rejected. Then they cannot be reduced to the same state.

Since no states in the 16 possible states can be reduced to one in all four possible cases as all four of them lead to a contradiction.
Hence, we get the conclusion that any DFSA that accepts L has at least 16 states. 

DFSA and REGEX

I found the second tutorial question this week was a little bit challenging for me. After spending one day for it (i am not smart =p), I got the solution here.  I feel great after finally my got the answer.

The question is as following:
Let L be the set of strings over {0, 1}* that begin and end with the same bit. Devise a regular expression, R that denotes L, and prove that your regular expression is correct.

My answer is as following:

R = 0 + 1 + 1(0+1)*1 + 0(0+1)*0

Claim:
 L(R) = L => L(R) is subset of L ^ L is subset of L(R)

Proof:
Suppose s is an arbitrary string in L(R). Since L(R) is a union of 4 smaller languages, We consider 4 cases.

    case 1 and case 2    s belongs to L(0) or s belongs to L(1)
        Then either s = 0 or s = 1 begins and ends with the same bit 0 or 1 respectively.

    case 3 and case 4    s belongs to L(0(0+1)*0) or s belongs to L(1(0+1)*1)
        Assume s belongs to L(0(0+1)*0) then by definition of the language denoted by R, s is in the form
        tuv where t belongs to L(0), u belongs to L((0+1)*), and v belongs to L(0).
        Same for the case that s belongs to L(1(0+1)*1).
        Thus s begins and end with the same bit.

    In all 4 cases, s begins and ends with the same bit, so s belongs to L
    As s is chosen randomly in L(R), we get the conclusion that every element of L(R) is also in L; that is, L(R) is subset of L.

Suppose s' is an arbitrary element of L, then we consider 2 cases: | s' | = 1 and | s' | > 1.

    case1: | s' | <= 1 =>  | s' | = 1
      The lone binary string of length 0 has neither a starting nor an ending bit to be the same as anything.
      A binary string of length is either 1 or 0 so it belongs to either L(0) or L(1). Since both L(0) and L(1) are subset of L(R), by inspection s' belongs to L(R).

    case 2: | s' | > 1
      In this case, the starting and ending bit of s' are the same but internal elements are different in s'. So s' is the form tut, where t belongs to L(0+1), and u is an arbitrary binary string over
     {0,1} , that is u belongs to L((1+0)*).

     We may ssume t belongs to L(0) as the same arguments follows if we interchange 0's for 1's.
     In this case, s' belongs to L(0)L((0+1)*)L(0) which belongs to L(R), so s' belongs to L(R)

   In both possible cases s' belongs to L(R). Since s' was choosen randomly, then every string of L is also a
   string of L(R). Hence, L is subset of L(R).

Since L(R) is subset of L and L is subset of L(R), we get the conclusion that L = L(R).

DFSA

This week, we introduced 2 new topics - formal language and FSAs. Basically, a formal language is a set of strings of symbols. FSAs, which stands for finite-state automaton, is a mathematical model of computation used to design a sequtial logic event.

Here is a easy and interesting example that is useful for understanding the topic.

Question: Devise a DFSA that accepts the language of a finite binary string whose length is a multiple of 3.

Solution:
My answer is as following:

where q0 is both the inital state and the end state because 0 is a multiple of 3 as well.
Every time after 3 numbers added (a multiple of 3), we reach the accepting state q0. 

bad term test

It was really bad unlike the first one because we have not much time to do it. Only fifty minutes for an unwinding, and 2 long proofs. Most of my friends had the same feeling, so I hope we would receive bell-curve.

An interesting question on the term test was to prove that 

c0 lg n <= T(n) <= c1 lg n which implies T belongs to big-theta (lg n).

To prove this question, I used the following structure

case1: c0 lg n <= T(n) 

           ...

           Then case 1 holds

case2: T(n)  < = c1 lg n
           ...

          Then case 2 holds

Then since both cases hold, we conclude that c0 log n <= T(n) <= c1 log n.
Then T belongs to big-theta (lg n)

Master Theorem

Today I learned Master Theorem. However, there are not many explanations on the course slides. I was still confused after I read the course notes because it doesn't mention what "d" is in the definition. So I found the clearer (for me, and hope helpful for others too ) version of Master Theorem here:

For the definition of T we have, we can easily use Master Theorem to find the bounds of T without unwinding.

In summary, when we have a definition of T and want to use Master Theorem, we do the following steps:

1. calculate n^log_ba

2. compare if f(n) either greater, less than or equal to n^log_ba
        if f(n) = n^log_ba , then T(n) = θ ( n^log_ba lg n)
        if f(n) < n^log_ba , then T(n) = θ ( n^log_ba)
        if f(n) > n^log_ba , then T(n) = θ ( f(n) )

The summary above just for general case, and understanding. For preciseness, please refer to the Theorem 4.1. =]

term test1 result and Predicate of Induction

I got my term test1 result today. I felt not bad when I just finished the test because I knew how to do every question. However the grade was not good for me. I made a mistake that shouldn't have happened.

As we made a predicate in such form "P(n): For every n belongs to N,13^n-1 = 12y where y is also a natural number. We prove that for all n belongs to N, P(n) by Mathematical Induction". We define what P(n) exactly is in this question, then we indicate that for all n belongs to N,P(n) and what type of Induction would we use. However, I wrote "P(n): For all n belongs to N,  and all y belongs to N,13^n-1 = 12y." which is completely wrong because we should use INDUCTION to do it . Then we can't say all n belongs to N inside the definition of P(n).

It seems like a stupid mistake. The test consists of 3 question and 5 marks each. It cost me 1 mark for every question. So due to this little problem, I lost 20%! I am so depressed about it. =[. That is my fault. I will do better next time and I won't make such a low level mistake any more! I will do better next time.

first midterm

I just came back from LM. Seems like could have a little break from the fast pace of preparing the test. Actually, i wanted to post a new blog yesterday when I was reviewing stuff. However i was too tired and fell in sleep. Haha, guess what? But I still took a picture last night, and it can show you the situation of last night instead of using words. Pretty hardworking right? (;p jkd)

For the preparation, I re-did every question on the
1. course slides
2. assignment
3. the sample test
4. I found the paper of last year.
After  a few practices, I found that the important thing is not just to write it, but we have to understand the principle behind a particular set of questions and better to find the pattern of the same kind of questions. For instance, when I see a question which asks about binary tree, the first thing I would think about is to divide the tree into left subtree and right subtree, then use complete induction to prove the statement is true. I have to make sure that I can solve a similar question use the particular induction method. That means I do understand how it works.
I was afraid that there will be one question like the round-robin tournament example on the week 3 slides. Honestly, I don't really understand this one which is the only one that I have no idea about. I will find the answer today. It is interesting.

ps.What on the test is easy to predict because all we have learned are four type of inductions. The probability of three of four, isn't it? ;p

LAND TO HERE

I had viewed a bunch of people's SLOGs before i started to write mine. The interesting thing here is that most of the first lines of those blogs are "Hello, World!"! Perhaps it's because that is the very first line that most programmers print in whatever language. =] I saw someone created their blog address as "i was force to make this slog" or something like that and someone even post a video named "Introduction to the theory of blogging "  It really makes me laugh out. Seems that SLOG is so much fun for us to learn this course.

This is my first time posting for my SLOG assignment. I am going to share more feelings, expriences, funny things and at times useful links or study methods in my blog. Hope my blog would help some students in this course.

Recently I am working on the next tutorial quesitons. I found that I am better on simple and complete induction rather than mathematical induction and well ordring. This pushed me to spend more time on the methods that I am not that skilled. Actually I searched more practices related to mathematical induction on internet and the materials from CSC165 as well. Wish I would do well on the quiz next week. =p

There is a SUPER useful link that contains teaching videos from wide topics of any level. This website gets thousands of videos of most of the subjects such as computer science, mathematics, algebra, calculus etc. and in a GREET ORDER.
www.khanacademy.org

sample video:

Hope you guys have fun with it. 

sep.25.2012

(posted on wrong website before.)  

TESTING TESTING

hi?
ignore me lol