Assignment Three Evaluation

Out of four questions, the hardest question for me was the question number one; Let L = {x in {0, 1}* | fourth-last symbol in x is 0 }. Prove that any DFSA that accepts L has at least 16 states. My first intuition of this question was really simple. There should be 8 states where the state accepts the claim because the fourth-last digit is always 0 but the first-last, second-last and third-last digit has to be different. Also, 8 states where the state rejects the claim due to the same reason. However, explaining my intuition did now follow the proper statements. My intuition does not even have a claim. Also, my intuition only explains the case where the number of state is 16. It does not explain further or lower cases. Therefore, I decided to use the proof by contradiction. I assume that the number of states can be lower than 16. Then at least two states from either rejecting state or accepting state have to be the same state. Then later states should be the same. If i can prove that the later sequences are different, I can prove that the claim is incorrect. Therefore, the number of states has to be greater than 16.

The rest of the questions were straight forward.I just needed to review the lecture slides and that was enough to prove the rest. 

One thing I realized from this assignment was that the number of pages I used to prove these questions. For assignment one and two, I did not use more than a few pages for each question. However, for this assignment three, I spent more than three pages to prove a single question. I think this is like a metaphor of CSC263 that it will take a lot longer to prove a single question.

NFSA and DFSA

NFSA stands for non-deterministic finite state automaton. DFSA stands for deterministic finite state automaton. My first intuition of these concepts were that these two ought to be a very different concept. Using this assumption, I was lost in the lectures and figured a few days later after searching online that these two concepts are relevant. DFSA is a finite state automaton where transition from a state to another is chosen in the first place. NFSA also allows states to transit from a state to another but for some cases, the transition is very ambiguous. That is why NFSA is called non-deterministic because transition is non-determined, while DFSA is called deterministic because transition is determined. They are also relevant because they can only recognize regular languages.

There is an example of NFSA online; in a binary string, determine if the input ends with 1.

This is pretty simple when the input is 0. However, problem raises when 1 is added. User does not know that if the the state has to be the accepting state or same as the current state. Due to this non-deterministic property, NFSA is called non-deterministic finite state automaton.

In my opinion using of NFSA is really bad idea because it needs further explanations to the readers. On the other hand DFSA seems really straight forward so that you do not need further explanation to understand the diagram.

As written above, the concept of DFSA is understood pretty well to me. However, NFSA is still ambiguous. I think I will ask the professor or search more examples online so that I can fully understand why NFSA is important. 

String and Finite States

Before discussing about finite states I will discuss some string definitions because the finite states will use string definitions to be proven. The common definition of alphabet is the standard set of letters which is used by some countries. In this computation theory, alphabet is a set of letters which can be combined to create a new word. A set of {b, e, r, d,s } is an example of alphabet. Alphabets can also contain numeric or non-characters. For example, {1, 5, 324, ㅎ, *, !} is also an example of alphabets. The notation for alphabet is S. String is a finite sequence of symbols over alphabet. 'boss' is an example of string from an alphabet set {a, b, o, s}. This string does not have to be the real word. Any combination from an alphabet set is still considered to be a string. From the previous example {a, b, o, s}, another example of string would be 'osboooba'. Obviously, this is not a real word. But this still is an example of string. Also, empty string is still an example of string. S* is the notation for the string. Language  is a set of strings from a set of alphabet. It can be empty or infinite. However, empty set and empty string are different things.
Finite States contain finite number of states where you can possibly move form one state. This is mostly used for creating electronic circuits. The state where you are currently at is called current state. You can also move from one state to another. This movement is called transition. From computation theory point of view, there is a transition formula where the condition is given in order to move from one state to another. There are two different states to the finite states. The first is accepting state. This state accepts an claim. The second is rejecting state. It rejects a claim.

For the finite states, there was an example question online; create a state machine which determines if a binary string contains even number of 1s. This is an easy example. You create two states; one called accepting state and the other called rejecting state. It will start from the accepting state because empty binary string is still considered to contain even number of 1s. For both cases, it transit to itself if 0 is added to the end. If 1 is added to the end, it moves to the other state.

For this strings, the concepts were really easy to understand because they all comes from the previous year studies. For example, python strings do not have to be the real world word. I found difficult was the state machine because the design of the finite state can vary from a person to another. I still understand that there is the best way to describe a finite state but finding the most efficient design was really hard for me. It would be extremely helpful if there was many examples but the class only covers a few examples. I think these are not enough to fully design an efficient finite state.
Upon learning of the string, it was extremely boring to me because it felt like we are reviewing stuffs that we learned long times ago. At the same time, finite states were not really new to me as well as the string because this is what I was learning in CSC258, a computer organization course from University of Toronto. However, it made a difference because it was still hard for me to develop a design in both classes. First intuition of this chapter was like 'I am so screwed.'
From the finite states, I decided that I should look up some questions regarding this topic because I know that I am really bad at this and I really want to improve on this.

Correctness Of An Iteration

There are several terminologies that I learned this week. Precondition refers to a condition before a loop iteration is starting. Some binary sort algorithm requires the list of numbers to be sorted in a certain way. Postcondition refers to a condition upon termination of the loop. Loop Invariant refers to the condition when an iteration finish. The loop invariant of the last iteration should be equal to the post condition and the every loop invariant should satisfy the precondition. If precondition, loop invariant, and termination happens, post condition is automatically satisfied. Precondition does not need to be proved because the condition depends on the user input. Loop invariant needs to be proved because if the loop invariant does not satisfy, the post condition cannot be satisfied. In order to prove the loop invariant, you let the current iteration to be i and the next iteration to be i+1. Why do we consider the next iteration? It is because the variables at i+1th iteration is same as the variables at the end of ith iteration. Termination needs to be proved too. Mostly, we do not need to use induction to prove because we can refer to the loop invariant to prove the termination. In order to prove the post-condition we simply prove precondition, loop-invariant, and termination. Then we match with the post-condition.
From this, I learned that this will be useful to create an algorithm. Sometimes, a loop falls into a infinite loop. Rather then using trial-and-error method, this proof should take longer but make more senses to me. From now on, I think I will briefly use this method to create a looping algorithm to make sure that the loop terminates and returns the value I wanted.

Assignment Two Evaluation

For the question one, it took more for me to come up with a pattern then the proving. I wrote down all the possible cases until the length of the binary string became 6 and found a pattern of P(n) numbers. However, I still had to figure out the reason behind. Otherwise, my proof will become an intuition or a guess. I found out that P(n-1) and P(n-2) are related to P(n) and this is somewhat similar to Fibonacci's sequence. From this question, I learned that finding a pattern might be the toughest step and the rest is easy. I think what we are learning in this course is more about finding pattern and the lectures are there to help us explain the pattern in words. From now on, I will look closer to the pattern when it comes to proving or coming up with an algorithm.
The question two was about expressing time complexity of a binary search algorithm. It was similar to the question we learned in a tutorial and a lecture. It was just that we did not go deeply inside the concept. First, I had to prove that the P(n) is non-decreasing. It was basically the one from the textbook. I proved the time complexity in two different ways. The first was by inequality and proving both upper bound and lower bound. The second was using the master theorem.

Time Complexity

The concept of time complexity was covered a few weeks ago. However, I did not want to record anything of it until I deeply understand the concept properly. Time Complexity is an quantifier of time taken of an algorithm. This is mostly used by the computer scientist to create the most efficient computer program. The chapter started with an example of recursive binary search. My first intuition about this algorithm was much focused into the code rather than the bigger picture. I had hard time to understand the lecture because I was trying to understand the code while my professor was looking at the bigger picture. From this, I learn that the detail about the codes do not really matter much in terms of time complexity. I have to look at the bigger picture where the recursion is happening and the condition of the recursion. For example, in this recursive binary search example, we assume that the array is sorted. We check the upper half recursively if the array at mid point is greater than a target. We check the bottom half recursively if the array at mid point is smaller or equal to the target. No matter how long the stopping point, the time complexity of a stopping point is one in general because only one or two lines are being executed. In order to find the big oh, the worst case, we take the maximum of the recursive functions. The maximum will return the most time taken to achieve the target given an array size.

Second thing I learned from this chapter is unwinding. Unwinding is expending or rewriting a recursive algorithm until it can be expressed as a closed form. Usually, the unwinding happens until number of steps reach the size of the input, n. The algorithm is usually simplified to a closed form, an expression in finite number rather than a recursive algorithm. When I tried the unwinding the first time, I kept expending until I found a pattern. However, this was a mistake. It is much crucial to expend to a a simplified form. For example, unwinding a Fibonacci sequence can generate a pattern of pascal's triangle;

F(n) = F(n-1) + F(n-2)

        = F(n-2) + 2F(n-3) + F(n-4)

        = F(n-3) + 3F(n-4) + 3F(n-5) + F(n-6)

        ....

It is true that there is a pattern but the pattern can hardly be implied to a closed form. Therefore, the following unwinding would be much easier to handle closed form;

F(n) = F(n-1) + F(n-2)

       = 2F(n-2) + F(n-3)

       = 3F(n-3) + 2F(n-4)

       = 5F(n-4) + 3F(n-5)

                 ....

At nth step, the first unwinding is so huge that it would be hard to compute. On the other hand, the 2nd unwinding has just two terms so it is much easier.

From this, I learn that sometimes finding a pattern is not really it. I have to think if this can be implied to a closed form. If it is impossible, I have to go back and find another pattern.

Term Test One Evaluation

After the Friday's lecture, the class had their term test one papers back. The term test consists of three questions.
The first question was about using a mathematical induction to prove a statement. The question was very similar to the tutorial question so the proving was extremely simple to write out. However, I lost a mark for not stating P(n). I thought that P(n) is basically the research question so I did not state the P(n) for this question. Unfortunately, the thought was wrong. I was right that P(n) is not equal to the research question but  P(n) comes from the research question. It was a basic mistake but taking off a mark out of 5 is too much. I admit that I deserve a mark deduction but losing 20% of a question is too much for a question when the question is about proving. From now on, I write out my P(n) before proving anything even though it is so obvious from the question.
The second question was about proving that a non-empty binary tree at height n has at most 2 to the power of n - 1. Like the first question, it was dealt during a tutorial so writing out a proof was an easy part. However, I lost another mark from stating P(n). For this time, I stated P(n) but I restricted the domain of the P(n). At first, I couldn't accept this deduction because the domain I stated is correct anyways. I asked my professor and the answer I got from him was kind of ambiguous to me. He first mentioned that I should never restrict the domain of P(n) because the domain is restricted later stating the P(n). However, logically, restricting twice, inside of P(n) and outside of P(n), does not change the statement. It would be inefficient but the statement would still be correct anyways. Second, he told me that a statement 'for a positive integer n' is equal to 'for all positive integer n' in this course so stating more than one 'n's is wrong. I still  could not understand this because 'a' and 'all' are different in the first place and we are not learning a so-called 'new English' for proofs. I think this is one thing that I need to accept anyways even though it does not really come to my mind because it is like a rule in order to show a proof. I will make this sure in my mind and never make this mistake again.
The third question was about the structural proof. I knew that it was in the midterm topics but did not expect this to come out because we did not have any tutorials dealt with this proof. Unfortunately, we had this proof and I got a bad mark on this one. For the next midterm and the final, I will cover everything that is in the topic list.