It is in week 11 now! Almost finish this course!
Now we are learning Regex and NFSA and DFSA. The last assignment is coming and it is about time comlexity and FSAs.
Most of the lecture material was not difficult to understand, but I was kind of confused by the difference between DFSA and NFSA. What I did this time was to look up definitions on the textbook. On the textbook, it said:
A deterministic finite state automaton (DFSA) is a mathematical model of a machine which, given any string input x, accepts or rejects x. The automaton has a finite set of states. including a designated initial state and a designated set of accepting states. While the definition of NFSA was that: In a DFSA, a given state and current input symbol uniquely determine the next state of the automaton.
To my understanding, the difference is that: in DFSA, the state only depends on the input, but in NFSA, the state depends on both the current input and also the given state.
BTW, I like drawing NFSA or DFSA, it was much more interesting than just to prove something using Induction or prove the correctness of a funciton.
2012年11月10日星期六
Midterm 2
Just finished my midterm two!
It was Ok~ I was so busy this week so I did not have lots of time prepare for it. But I think it will be fine since I did not have questions remained from the lectures before.
I got 100% on my assignment one! I am sooooooooo happy!!!!
Hope my assignment two will be still good!
It was Ok~ I was so busy this week so I did not have lots of time prepare for it. But I think it will be fine since I did not have questions remained from the lectures before.
I got 100% on my assignment one! I am sooooooooo happy!!!!
Hope my assignment two will be still good!
2012年11月3日星期六
Assignment 2
I just submitted the second assignment. In general, I found the second assignment was harder than the first one.
There were two questions in this assignment. Sounds not much, but each question was very long. The first question asked us to unwind first and then prove the closed form. It was very much like a question that was in one of the tutorial. So what I did was to review the tutorial question first and then try to do the question myself. The unwinding was not very complicated for me and since I was pretty clear with Simple Induction and Complete Induction, I solved the first question without too much difficulties.
The second question was about what we learnt in the last week -- time conplexity. I was so glad that I solved all questions that I didn't understand last week so now I was very clear about what steps should I do. If I did not fix my problem last week, I would be confused about how to do this question and it was going to take me a lot of time if I googled online or read through all the pages on the textbook. So, Never Put Off Until Tomorrow What You Can Do Today. ^_^
This week we mainly learnt about proving the correctness of a function.
To prove the correctness of a function. We need to prove that under the assumption that precondition holds, the function terminates and the post condition holds. To prove the function terminates, we have to construct a decreasing sequence in N and then use well-ordering principle to prove that there is a smallest value in N so that the loop will finally terminate.
The second midterm is in next week. I need to read through the text book as much as I can and clear all my questions before the test. Oh~ and do not make the same mistakes again as in Midterm test one. Cheer up and be ready! ^_^
2012年11月1日星期四
Midterm Paper Back
Got my midterm back! But I was not so happy with my grade.
The questions were not so hard. I lost marks mostly for the structure and the induction hypotheses. I think I am going to professor's office hour and ask for suggestions. Hope I won't make the same kind of mistake in the second midterm test.
Looking forward to get my assignment one back!
2012年10月27日星期六
Master Theorem
In week 7 we learnt about Master Theorem.
I found Master Theorem was very interesting and it was an easier way to find the upper and lower bound. But one problem (at least it was a problem for me) was that I had to remember the three different cases. I liked to use method in week 6 better than this because I did not like to cram something without knowing how to get the conclusion.
Have a nice week!
2012年10月20日星期六
Time Complexity
Now it is in week 6, half of the fall semester! Wow, time is so fast!
Course topic now is about Time Complexity. This is very similar to what I learnt in CSC165. But since I did not understand time complexity well in CSC165, I listened to the lecture carefully and will go to office hour to ask any questions that pops up in my mind.
We are learning complexity of recursive functions. Unwinding is a mostly used way to find the lower and upper bounds of a function. This is a different approach from how find the lower bound in CSC165. First, develop a special case and then apply for more general case, for example, first suppose n to be the power of 2 and then apply n to arbitrary numbers.
But there was one thing that I did not understand in class this week. Professor drew a picture to prove that a function was non-decreasing. I did not understand how this picture related to the decreasing of a function. So I went to the section on Thursday night. After the lecture, I asked professor Heap what did this graph mean. The professor explained patiently that since at first we supposed n to a power of 2 and this was not a general case, we wanted a more general case to apply to the unwinding. To apply the unwinding to a general case, we used the upper and lower bound of log(n) to get an arbitrary number. First prove T was not decreasing and then used the relationship between n and n nod and the unwinding to develop an inequality that contained T(n) on one side of the unequal sign and n on the other side. In this way, we could find out both the upper bound and lower bound of a function.
After professor's Heap's explanation, I found I got a better understanding of how to develop the upper and lower bound for a function. Asking questions to professor helps a lot. He can always explain things well and he is very patient. ^_^
Course topic now is about Time Complexity. This is very similar to what I learnt in CSC165. But since I did not understand time complexity well in CSC165, I listened to the lecture carefully and will go to office hour to ask any questions that pops up in my mind.
We are learning complexity of recursive functions. Unwinding is a mostly used way to find the lower and upper bounds of a function. This is a different approach from how find the lower bound in CSC165. First, develop a special case and then apply for more general case, for example, first suppose n to be the power of 2 and then apply n to arbitrary numbers.
But there was one thing that I did not understand in class this week. Professor drew a picture to prove that a function was non-decreasing. I did not understand how this picture related to the decreasing of a function. So I went to the section on Thursday night. After the lecture, I asked professor Heap what did this graph mean. The professor explained patiently that since at first we supposed n to a power of 2 and this was not a general case, we wanted a more general case to apply to the unwinding. To apply the unwinding to a general case, we used the upper and lower bound of log(n) to get an arbitrary number. First prove T was not decreasing and then used the relationship between n and n nod and the unwinding to develop an inequality that contained T(n) on one side of the unequal sign and n on the other side. In this way, we could find out both the upper bound and lower bound of a function.
After professor's Heap's explanation, I found I got a better understanding of how to develop the upper and lower bound for a function. Asking questions to professor helps a lot. He can always explain things well and he is very patient. ^_^
2012年10月14日星期日
Feel much better for Structual and Well-ordering Induction
The midterm test made me feel I need more understanding in Structural and Well-ordering Induction.
I googled on line but could not find much useful explanation. But luckily I remembered we have a discussion board. I went to the discussion board and found with no surprise that I was not the only one who did not understand Structural and Well-ordering Induction well. In the specific tag, somebody provided a pdf that explain Structural and Well-ordering Induction. I opened the file and as I read through, I found this file very helpful. It solved my problems that when should I use Well-ordering Induction and also explain the difference between Structual induction and Simple Induction. To my undertstanding, Structural Induction could use Simple Induction as an approach to prove things. If we want to prove something that has a specific structure, we could use Structural Induction.
Well-ordering Induction is more likely to use during a provement. It does not like Simple Induction or Complete Induction that have a certain format, it is used as a part of the provement. I remembered professor Heap said it is more often used in the material we are going to learn in a few weeks.
I googled on line but could not find much useful explanation. But luckily I remembered we have a discussion board. I went to the discussion board and found with no surprise that I was not the only one who did not understand Structural and Well-ordering Induction well. In the specific tag, somebody provided a pdf that explain Structural and Well-ordering Induction. I opened the file and as I read through, I found this file very helpful. It solved my problems that when should I use Well-ordering Induction and also explain the difference between Structual induction and Simple Induction. To my undertstanding, Structural Induction could use Simple Induction as an approach to prove things. If we want to prove something that has a specific structure, we could use Structural Induction.
Well-ordering Induction is more likely to use during a provement. It does not like Simple Induction or Complete Induction that have a certain format, it is used as a part of the provement. I remembered professor Heap said it is more often used in the material we are going to learn in a few weeks.
订阅：
博文 (Atom)