DFSA

DFSA or Deterministic Finite State Automaton is  a way to tell machine to react with particular input. Coming up an DFSA is quite easy but at the same time it can be challenging if more than one requirement is need to be fulfilled. Hence, there is certain tactics that we can use to create a DFSA.

First of all, if there is more than one condition need to be fulfilled, then create different DFSA for each condition, then try to combine both of the DFSA to come out with new DFSA which will match both requirement.

In order to prove the DFSA, we need to first generate a transition function for the diagram that we build. Then from that transition function we can come out with a extended transition matrix, which will describe each state of DFSA. This is a good way to know whether our DFSA will work for all inputs and outputs. 

Algorithm and it's proof.

Coming up an algorithm is hard enough and proving that it works is even harder. To prove algorithm, there is certain steps that we have to follow:

               1. Determine Pre-condition.

                              Pre- conditions are the requirement that we impose, so that our algorithm can work.                Pre-condition must be reasonable and doesn't directly related to post-condition.

              

               2. Determine Post-condition.

                              Post-condition is the output that we want from this code, not only for the return value                but we also can set post-condition for each variable that the code uses.

               3. Come out with Induction Hypothesis

                              One of the hardest thing in the proof is coming out with an IH. The IH must combine                pre-condition to post-condition.

               4. Proof by induction.

If all the 4 steps are followed correctly, then most probably we can proof the algorithm. However, the last step is very important and quite hard.

Proofing Iteration.

Proving iteration might follow the same steps but before coming up with IH, we need to identify our loop invariant. Loop invariant is the thing that does not change during iteration. The loop invariant is very useful when proving the loop as well as when proving that the loop will end. In order to prove the iteration, it's better to split the proof into two proof.

               Partial Proof:

                              Prove that the loop will satisfies post condition if the loop terminates.

              

               Termination Proof :

                              Prove that the loop will terminate. 

Divide and Conquer!

   As I promised in last blog, in this blog I will talk about the limit of number of time the recursion function is called.

   There is two way of getting the limit of recursion function. In first way, I must get a closed form of  the recursive function, then from that I can deduce the either worst case scenario or best case scenario. Then I will use the first case scenario I've proved to prove the other case scenario.  This is fairly simple and intuitive.

   However, I can't get closed form all the time, and even if there is closed form, there is another way of proving the limit without getting closed form. In that case, Master Theorem will be very useful. The Master Theorem is very useful when I'm doing divide and conquer. "Divide" involves breaking the array or list in a particular manner. While in conquer part, I've to worry about additional steps that involved with combining all the "divided".

Master Theorem looks like :

               Assume T(n)        = k                                                      if  n<B

                                             = a₁T(n/b_k) + a₂T(n/b_k) + f(n)          if  n>B

               T(n)        = θ(n^d)                 if a < b^d

                              = θ(n^d log n )      if a = b^d

                              = θ(n^log­_b^a)           if a > b^d

               Hence, a = a₁ + a₂

                              b = b_k

                              d = power of limit of f(n)

   For more information about Master Theorem http://en.wikipedia.org/wiki/Master_theorem. The link helped me to understand better about Master Theorem. 

Unwinding

I'm really sorry for inactive blog for about one month. So there are a lot of things to talk about. Hence, I will split this week blog to three blogs to cover up my pass weeks.

First, I want to talk about my experience in proving limit from a recursion function. The number of recursion function can be called  is in between its best case scenario to worst case scenario. Hence, in order to proof  the limit, first we need to find closed form of recursion function. Then we need to find the best case and worst case scenario for that closed form.

From my experience, getting closed form is the hardest thing to do in proving the limit of recursion function. Even though prof, taught us to do unwinding steps before getting to closed form but it is quite hard to see the pattern from unwinding. In order to recognize the pattern I need to do quite a lot of revision of my previous calculus subject. Even if I do recognize the pattern there is another problem, finding the closed form. Sometime, the pattern is obvious and we can straight away get the closed form, but sometime the pattern is obvious but not the closed form. For example Fibonacci sequence because the pattern might be to see, but getting closed form is not easy.

So in the next blog I will talk about getting limit of the closed form. However, once you found closed form the next problem is just a cake walk :D 

Exponential vs Quadratic

Exponential vs Quadratic

A1 is done.....

This is the first time I'm blogging (not sure whether that's the right verb?!) and I'm bad at taking notes or keeping journals up-to-date. Hopefully this SLOG program will help me.

I'm not good at introducing myself but I'll give a shot. I'm second year student in Computer Science Specialization and I'm a transfer student from UTSC. Well, that's it... I told you I'm not good at this.

The weekend was not as good as I expected but it could have been worse. At least, I was able to solve A1 without much trouble. I do know about induction techniques before starting the course but I have never been comfortable with it. So, that was one of the reasons why I started A1 earlier than I usually do. In the past I always had problems with induction and induction hypothesis, I couldn't really see the logic behind proving a question by using induction. But now I understand that induction is fully based on induction hypothesis and I must use the induction hypothesis somewhere in the proof. That might be very obvious for me right now, but it wasn't in the past.  But I still confused about structural proof, I need more time to understand about that technique. I'm not sure whether induction proofs only works for natural numbers or  right now CSC236 is focusing induction with only natural numbers.

Anyway, the best part of the A1 is it must be fully typed. For once, I don't have to worry about my handwriting  At the same time, I get frustrated with MS Word's equation format, I wish there was shortcuts for (for all, elements of) symbols. Otherwise, I'm quite happy with "no-handwritten" rule especially after seeing how many times I've pressed Ctrl-Z and Ctrl-Y.


Well, midterm season is coming and I'm not quite prepared especially for my elective course. For now I just want to enjoy watching weekend soccer (football) matches!