Assignment 3 was due on Monday night, and still our group couldn't figure out the very last question. DFSA wasn't not my specialty, but since other members were busy with error corrections and putting the answers together with nice and neat copy, I was mainly in charge of the question #4. With help of TAs and peers, I could set up two different DFSAs, one deals with odd length of binary strings, and the other deals with multiples of 5 and found the intersection DFSA of those two DFSAs. It was difficult to define the DFSA just by wording, but I think I had fully explained how it operates.
Week 13, will be my worst week in the term, there are 3 assignments and 2 tests waiting for me.
Hope there won't be any overnight staying at BA, but it is much more likely to be happened.
I feel blurry about NFSA, but this time, I will be prepared before the test.
Monday, December 1, 2008
11th Week - SLOG
This week, we continously had learned the concept of FSA. This time, in addition to DFSA, NFSA was introduced. From the lecutre, we saw that a regular DFSA is a special case of an NFSA and for every regular expression, there's an equivalent NFSA.
There was also the last problem set due on Friday's lecture and it was very simple, since we had went over a similar example from last week's lectures. Just by looking at it, L(((0+1)(0+1))*(0+1)) was for sure, binary strings of odd length , because addition of 1 to multiples of even length always equals odd length, and the regular language was only consisting of 0s and 1s, which is a definition of binary language.
Rough copies of Question #2 from A3 was prepared, earlier than what I had thought, because the questions had very similar concept to the problem set, which dealt with the regular expressions. I will continue to work on A3 over the weekend.
There was also the last problem set due on Friday's lecture and it was very simple, since we had went over a similar example from last week's lectures. Just by looking at it, L(((0+1)(0+1))*(0+1)) was for sure, binary strings of odd length , because addition of 1 to multiples of even length always equals odd length, and the regular language was only consisting of 0s and 1s, which is a definition of binary language.
Rough copies of Question #2 from A3 was prepared, earlier than what I had thought, because the questions had very similar concept to the problem set, which dealt with the regular expressions. I will continue to work on A3 over the weekend.
Sunday, November 30, 2008
10th Week - SLOG
In the lecture this week, We continued to looking at the regular expressions and its algebraic relations. It was very interesting that like algebraic equation, regular expressions also shared the laws of distribution, associativity, empty set, and other identities. Exmaples were consists of proofs, asking us to show whether two regular languages means the same or not by using above laws and identities.
The problem set #5 was stright forward, It can be done by using the basic definitions of regular expression and languages on the text book.
The problem set #5 was stright forward, It can be done by using the basic definitions of regular expression and languages on the text book.
9th Week - SLOG
Test#2 was in Friday's lecture, but I couldn't make it due to illness. Light cold started on Wed. got worse and I couldn't even walk out of my bed. When I feel bit better, I went to see a doctor, and he confirmed that I was not in a good condition for the test.
Although, I couldn't make to the test and lectures, I kept reviewing the course notes and tried to understand the material. Fortunately, I have seen regular expressions before when I was in CSC207, so It wasn't that diffcult to catch up. Some times, I think the symbol L and R backward each other, but I will figure it out, when I get used to it.
Although, I couldn't make to the test and lectures, I kept reviewing the course notes and tried to understand the material. Fortunately, I have seen regular expressions before when I was in CSC207, so It wasn't that diffcult to catch up. Some times, I think the symbol L and R backward each other, but I will figure it out, when I get used to it.
8th Week - SLOG
On Monday, our group mainly focused on finishing the very last question of A2. Like I wished, there was a question on the run-time complexity, so I was the one who mostly in charge of that question. It wasn't very hard to derive the formula from the steps, but proving that T(n) in Theta was very difficult, even considering it as a bonus. I had to search my memory back to CSC165 where I had learned bigO and omega stuff, but couldn't really figure out how to. Fortunately, with help of TA, I could write at least something down, but I was not really sure, if i will be able to earn bonus or not. Hopfully, the prof. will be generous on marking the bonus.
On this week's lecture, we continued to learn the proofs of correctness of algorithms. The concept of iterative correctness was introduced and I found the iterative case much difficult than the recursive case, mainly because of the invariants.
I will spend my time over this week to review the usage of loop invariants to iterative cases, so I can fully understand the concept.
On this week's lecture, we continued to learn the proofs of correctness of algorithms. The concept of iterative correctness was introduced and I found the iterative case much difficult than the recursive case, mainly because of the invariants.
I will spend my time over this week to review the usage of loop invariants to iterative cases, so I can fully understand the concept.
7th Week - SLOG
On this week's class, we had covered the correctness of algorithm. Two examples were shown; recursive binary search, and greatest common divisor. In the recBinSearch, by using the condition variables in the code, we had set up P(n) statement and we proved that precondition implies to postcondition and we did the same with great common divisor.
Problem Set #4 was not hard, I needed to review an examples from the lecture notes and just little time to think about its application to the question then I could get the proof that the precondition implies to the postconditon.
Problem Set #4 was not hard, I needed to review an examples from the lecture notes and just little time to think about its application to the question then I could get the proof that the precondition implies to the postconditon.
6th Week - SLOG
On the week 6, we have covered the sections of merge sort and runnig time. This is the first topic that I found amusing, since these topics directly involves with programming languages. I found it very fun to track the codes down and derive a run-time formula from those codes.
Like some other algorithms (eg. trees), the merge sort also uses divide-and-conquer, in the application with the programming codes, It takes the unsorted list, and divide the list into two subcategories, sort them using recursion and put two lists back to one complete sorted array. I found it easier to understand than the trees, because proving trees varies every time, depending on their types, but the merge sorts, its proof structure seems remaining always the same, but the numbers.
I can't wait for the A2 to come out, because I feel very excited to learn these!
Like some other algorithms (eg. trees), the merge sort also uses divide-and-conquer, in the application with the programming codes, It takes the unsorted list, and divide the list into two subcategories, sort them using recursion and put two lists back to one complete sorted array. I found it easier to understand than the trees, because proving trees varies every time, depending on their types, but the merge sorts, its proof structure seems remaining always the same, but the numbers.
I can't wait for the A2 to come out, because I feel very excited to learn these!
Subscribe to:
Posts (Atom)