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.
Sunday, November 30, 2008
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.
Subscribe to:
Posts (Atom)