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!
5th Week - SLOG
First term test was done, but not satisfied at all. I couldn't make much improvement on finshing a question within a limited amount of time. I was keep rushing during the test, worring whether if i can finish it on time or not. I had to leave many blanks as I read through out the questions, because I knew for sure that I can't finish it within a time limit. I was mainly focused on writing the structure down first and think about the algorithms later on. The difficulty of the test was a fair game and may be that is a reason why I am still regreting.
4th Week - SLOG
This week, we have covered materials on recursion. Although the concept of recursion in which a function is repeating within its own definition, was not new to me, because of CSC148, Its relation to induction was very interesting. In the lecture, various examples were covered, including the Fibonacci sequence and the golden ratio.
Test 1 is scheduled in next Friday's lecture, and since we don't have any problem sets or assignments to finish, It is a good time for study and review the materials that we have covered in the course over this weekend. I am still worried that I take too long to finish up a question, but hopfully I will be improved before the test.
Test 1 is scheduled in next Friday's lecture, and since we don't have any problem sets or assignments to finish, It is a good time for study and review the materials that we have covered in the course over this weekend. I am still worried that I take too long to finish up a question, but hopfully I will be improved before the test.
Saturday, November 29, 2008
3rd Week - SLOG
It is already been three weeks from the first day of the lecture.
Now I feel more comfort on the concepts of both inductions,
but the new topic from this week bothers me very much.
By using the round-robin domino example from the lecture notes, It wasn't very hard to understand the definition of the well-ordering principle: every "non-empty set" of positive elements contains a minimal element. but its approach to solving a problem is still a mystery to me. because to me, it is a common sense to know that there is always a smallest element in a set, if the set is non-empty, but questions always asks me to prove "logically" this type of thing...
but I believe that like I couldn't find anything in common between binary tree and inductions,
I will find in someday the connection between well-ordering and the logic as I move along the course.
Now I feel more comfort on the concepts of both inductions,
but the new topic from this week bothers me very much.
By using the round-robin domino example from the lecture notes, It wasn't very hard to understand the definition of the well-ordering principle: every "non-empty set" of positive elements contains a minimal element. but its approach to solving a problem is still a mystery to me. because to me, it is a common sense to know that there is always a smallest element in a set, if the set is non-empty, but questions always asks me to prove "logically" this type of thing...
but I believe that like I couldn't find anything in common between binary tree and inductions,
I will find in someday the connection between well-ordering and the logic as I move along the course.
Second Week - SLOG
On the second week of the class, the first problem set was due.
The questions were very straight forward, especially the first question about the proof of unit digits.
Since it wasn't the first time introducing the concept of induction, it was not a hard task to write down a proof following a proper structure. Although I still required plenty of time to think the logic neccesary for a given question to write more precise and neat proof.
But I strongly believe that I will overcome this in someday by trying out more questions.
In the lecture, a concept of complete induction had introduced. the concept was very similar to the ones that are simple inductions, but instead of proving p(n+1) from p(n), we assumed all the cases before n are true, and prove p(n) by using those cases.
I assume this will be used for the upcomming problem set #2 and assignemnt #1.
The questions were very straight forward, especially the first question about the proof of unit digits.
Since it wasn't the first time introducing the concept of induction, it was not a hard task to write down a proof following a proper structure. Although I still required plenty of time to think the logic neccesary for a given question to write more precise and neat proof.
But I strongly believe that I will overcome this in someday by trying out more questions.
In the lecture, a concept of complete induction had introduced. the concept was very similar to the ones that are simple inductions, but instead of proving p(n+1) from p(n), we assumed all the cases before n are true, and prove p(n) by using those cases.
I assume this will be used for the upcomming problem set #2 and assignemnt #1.
Friday, September 19, 2008
First Week - SLOG
It's already been a second year, since I was here at the U of T.
CSC165 that I took previously for this course, was definately not a course for me.
I had a rough time to finish up proofs; that was just a nightmare...
Now, I am in CSC236, with more course load, with more difficult concepts of proof.
However, the first week of lectures were much better than what I had expected.
For the first two days, the prof. spent much of the time on reviewing the concepts of induction proofs. Light and Bold; these are the words that I would define the examples from the lectures.
The examples help me a lot on making me go on track, thoroughly understanding basic procedures of induction proofs and refreshing my memory.
On the last day of the class, the 'real' one had been arrived. New material was introduced, and
It was interesting in a way that the induction proofs can be done by cases.
I am still bit blurrly , in what cases do we required to use this concept,
but i will find it out while i work on the assignments or problem sets.
In general, the first week of classes went fairly well.
Thanks to the prof. for smooth lecturing :)
CSC165 that I took previously for this course, was definately not a course for me.
I had a rough time to finish up proofs; that was just a nightmare...
Now, I am in CSC236, with more course load, with more difficult concepts of proof.
However, the first week of lectures were much better than what I had expected.
For the first two days, the prof. spent much of the time on reviewing the concepts of induction proofs. Light and Bold; these are the words that I would define the examples from the lectures.
The examples help me a lot on making me go on track, thoroughly understanding basic procedures of induction proofs and refreshing my memory.
On the last day of the class, the 'real' one had been arrived. New material was introduced, and
It was interesting in a way that the induction proofs can be done by cases.
I am still bit blurrly , in what cases do we required to use this concept,
but i will find it out while i work on the assignments or problem sets.
In general, the first week of classes went fairly well.
Thanks to the prof. for smooth lecturing :)
Subscribe to:
Posts (Atom)