In the last week two weeks of class, Professor Heap talked more about Finite State Automata and Languages--specifically about Deterministic FSA, Non-Deterministic FSA, State Elimination, etc. I didn't quite understand the difference between Deterministic FSA and Non-Deterministic FSA at first because I didn't even know what "deterministic" means in this case. Anyhow, I studied from the slides, and the examples presented in class really helped. Also, I found the last two tutorials very helpful--the exercises were really intuitive and so the quizzes seem so easy.
The last assignment was kind of tricky. I didn't spend too much time on the first two assignments, but I somehow got stuck on the second question. I didn't know clearly understand the hint for this question, so I tried to prove a bunch of different loop invariants to refer to when showing termination. So I sent an email to ask Professor Heap about the question, and I managed to finish it like 10pm on the due date. What a relief.
Wednesday, December 5, 2012
Sunday, November 25, 2012
Finite State Automata and Formal Languages
In the past two weeks, Professor Heap has been talking about Finite State Automata and Formal Languages. I learned about Finite State Machine in a third-year course about digital logic and computer design, so I'm pretty familiar with how to construct a state diagram / graph and such. However, I had never heard of the term "formal languages" back in the day when I was taking the course, so I was kind of excited to know what it really means and what it is about.
I came to realize that it is just another basic topic in Computer Science. I was kind of confused at first about how alphabets makes a string and how strings make a languages, but when I gave myself some time to think about it, there is really nothing to think about because the topic is simple as it seems. Moreover, I learned about Regular Expression in a second-year Software Engineering course, and also in csc209 (which I'm taking). To be specific, I had to learn how to use regular expressions when programming in Unix or using the shell. I don't know why it is taught in this course when presumably every CS student has to take csc207 or csc209 and learn to really use regular expressions.
Anyways, the way the material was presented in class was okay. It might be better if the pace of the class is a little bit faster. Perhaps there should be less interaction between the professor and the students. For example, at the end of the Friday class (last week), Professor Heap was constructing a state diagram /graph, and he encountered some problems. The students were suggesting solutions, and Professor Heap was willing to listen to everyone, which is great because the students get to participate and be more involved in the class, but I think he should have tried to fixed the problems and answer questions and sometimes keep the pace or consistency of the class up.
Both the tutorial exercise and the quiz on November 20 were way to easy compared to the previous ones, but that's not something to complain about (lol).
I came to realize that it is just another basic topic in Computer Science. I was kind of confused at first about how alphabets makes a string and how strings make a languages, but when I gave myself some time to think about it, there is really nothing to think about because the topic is simple as it seems. Moreover, I learned about Regular Expression in a second-year Software Engineering course, and also in csc209 (which I'm taking). To be specific, I had to learn how to use regular expressions when programming in Unix or using the shell. I don't know why it is taught in this course when presumably every CS student has to take csc207 or csc209 and learn to really use regular expressions.
Anyways, the way the material was presented in class was okay. It might be better if the pace of the class is a little bit faster. Perhaps there should be less interaction between the professor and the students. For example, at the end of the Friday class (last week), Professor Heap was constructing a state diagram /graph, and he encountered some problems. The students were suggesting solutions, and Professor Heap was willing to listen to everyone, which is great because the students get to participate and be more involved in the class, but I think he should have tried to fixed the problems and answer questions and sometimes keep the pace or consistency of the class up.
Both the tutorial exercise and the quiz on November 20 were way to easy compared to the previous ones, but that's not something to complain about (lol).
Monday, November 19, 2012
Recursive & Iterative Algorithm Proofs
In the last three or four weeks, Professor Heap talked about proving the recursive and iterative Binary Search algorithms. I found them confusing because we never had a chance to really work on the any problem since we had a midterm was on Monday instead of the tutorial, and the next tutorial was Reading Break, and the tutorial exercises and quiz for today's tutorial were about the new topic: Automata and Formal Language, which I will talk about in the next post.
The way the material was presented in class was good enough, although the professor did't really do anything much except going through the proof, and the students get to ask questions--which was probably the way it should be. However, sometimes I feel like I don't know what to ask because I knew nothing about the topic when it was introduced. Perhaps I should try to spend some time trying to understand some of the material like the motivation or the introduction of the topic and going through the slides before each class. That way, I should be able to come up with good questions to ask in class and have a better grasp of the material at the end of the class.
I personally don't think learning to prove the recursive or iterative algorithms will be very useful later (in later years or when working in the CS field). I mean the techniques for proving the correctness of algorithms, recursive or whatever, is crucial, but there is too much format in what we are doing here. For example, we need to prove the pre-conditions and the post-conditions in our Proof by Induction, and we need to also show that the pre-conditions imply the program termination. As for the iterative algorithm proof, we need to show the partial correctness (i.e. everything is correct at ith iteration). But in reality, I don't think proving the correctness of algorithms will really follow these patterns.
The way the material was presented in class was good enough, although the professor did't really do anything much except going through the proof, and the students get to ask questions--which was probably the way it should be. However, sometimes I feel like I don't know what to ask because I knew nothing about the topic when it was introduced. Perhaps I should try to spend some time trying to understand some of the material like the motivation or the introduction of the topic and going through the slides before each class. That way, I should be able to come up with good questions to ask in class and have a better grasp of the material at the end of the class.
I personally don't think learning to prove the recursive or iterative algorithms will be very useful later (in later years or when working in the CS field). I mean the techniques for proving the correctness of algorithms, recursive or whatever, is crucial, but there is too much format in what we are doing here. For example, we need to prove the pre-conditions and the post-conditions in our Proof by Induction, and we need to also show that the pre-conditions imply the program termination. As for the iterative algorithm proof, we need to show the partial correctness (i.e. everything is correct at ith iteration). But in reality, I don't think proving the correctness of algorithms will really follow these patterns.
Saturday, November 10, 2012
2nd Term Test: Repeated Substitution and Big-Theta Proof
Even though the marks are not out yet, I know I somehow screwed up the second term test. The first question of the test was a two-part question about recurrence relation--the first part is to use repeated substitution or unwinding to solve for the closed form of the recurrence relation, and the second part is to prove that the closed form is correct using induction. I'm very familiar with both of these types of questions, yet I failed to get the closed form of the recurrence relation because I couldn't figure out the closed form for the sum/series at the very end. I believe it was something like: 1+4+16+64+... = 4^0 + 4^1 + 4^2 + 4^3 + ...
As a result, I could not prove that my closed form was correct by induction--simply because I did not have the correct closed form. Moreover, since the term test has only two questions, it's kind of like "you either get an A or a C"--you screwed up one question and there goes half the marks.
The second question was to prove that some recurrence relation is in Big Theta n squared or something. This is very similar to the last question--which I believe I did it correctly--on the second assignment. On the term test, though, I forgot the very last step where you simply create the final, suitable upper/lower bound. For example, from the BigO part of the question on the second assignment, when you get T(n) <= 2 + log n, you just say that this is less than or equal to 2logn + logn = 3logn for n >= 2 simply and obviously because 2 <= 2logn for n>= 2.
So I did really bad on the term test and would be lucky to pass the test. I didn't see this coming but kind of deserved it though--I barely studied before the test because I had no motivation at all. Nonetheless, I will be looking forward to picking it up and doing well on the last three or four quizzes and preparing for the final exam. Bring it on!!
As a result, I could not prove that my closed form was correct by induction--simply because I did not have the correct closed form. Moreover, since the term test has only two questions, it's kind of like "you either get an A or a C"--you screwed up one question and there goes half the marks.
The second question was to prove that some recurrence relation is in Big Theta n squared or something. This is very similar to the last question--which I believe I did it correctly--on the second assignment. On the term test, though, I forgot the very last step where you simply create the final, suitable upper/lower bound. For example, from the BigO part of the question on the second assignment, when you get T(n) <= 2 + log n, you just say that this is less than or equal to 2logn + logn = 3logn for n >= 2 simply and obviously because 2 <= 2logn for n>= 2.
So I did really bad on the term test and would be lucky to pass the test. I didn't see this coming but kind of deserved it though--I barely studied before the test because I had no motivation at all. Nonetheless, I will be looking forward to picking it up and doing well on the last three or four quizzes and preparing for the final exam. Bring it on!!
Friday, November 2, 2012
Divide and Conquer: MergeSort
This will be my second post for the weekend since I will be way too busy during the upcoming week. In this post I will discuss the topics covered in the last two weeks including the divide-and-conquer algorithm.
Divide and Conquer, to me, is one of the concepts in Computer Science that I actually find useful. It helps you tackle complicated problems and makes you think more like a computer scientist.
Although I have forgotten all the details like the pseudo-code of the MergeSort and etc., I didn't find the material presented in class to be surprising or anything. In the last tutorial, though, I was caught a bit off guard when the quiz was to write a divide-an-conquer algorithm--for a very similar problem to one of the tutorial exercises, but my head was blank because I just had a tough midterm that morning. Anyway, what's the big deal? it's just a type of recursion, I just need a base case, and then divide the problem into sub-problems. Sounds easy, but the thing is the index. I let m=(b+e)/2 and there I was thinking if m would be the ceiling or the floor, and then I thought maybe it doesn't matter, but then do I verify A[m-1], A[m], or A[m+1], and would the lower list be from b to m or m-1, etc.
I barely finished the quiz in time that day; hopefully, I didn't make any mistake. I have been thought this before. A few similar problems, and I should be ready for the midterm. I doubt if I will have time to prepare for the midterm though...
Divide and Conquer, to me, is one of the concepts in Computer Science that I actually find useful. It helps you tackle complicated problems and makes you think more like a computer scientist.
Although I have forgotten all the details like the pseudo-code of the MergeSort and etc., I didn't find the material presented in class to be surprising or anything. In the last tutorial, though, I was caught a bit off guard when the quiz was to write a divide-an-conquer algorithm--for a very similar problem to one of the tutorial exercises, but my head was blank because I just had a tough midterm that morning. Anyway, what's the big deal? it's just a type of recursion, I just need a base case, and then divide the problem into sub-problems. Sounds easy, but the thing is the index. I let m=(b+e)/2 and there I was thinking if m would be the ceiling or the floor, and then I thought maybe it doesn't matter, but then do I verify A[m-1], A[m], or A[m+1], and would the lower list be from b to m or m-1, etc.
I barely finished the quiz in time that day; hopefully, I didn't make any mistake. I have been thought this before. A few similar problems, and I should be ready for the midterm. I doubt if I will have time to prepare for the midterm though...
Solving Recurrence: Repeated Substitution and Closed Forms
Although I have learned repeated substitutions before, I just recently learned that you can have another recurrence in your "closed form" as long as it's not a recursive function of the same variable. I never knew this until the third tutorial when the TA was solving a recurrence relation which kind of "contains" the fibonacci recurrence. I found this surprising at first because I always thought of a close form as "something I can plug in a given value of the variable and get the output".
Monday, October 29, 2012
Well-Ordering and Structural Induction
Professor Heap talked about Well-Ordering and Structural Induction in the third and the forth week. I had never heard of either of them and found them a bit confusing at first. I thought Well-Ordering was some kind of a proof technique and I couldn't figure out what it really means. However, after I spent some time reviewing my notes and examples presented in class, I learned that Well-Ordering is just like a fact: every non-empty set of positive integers contains a smallest element (http://en.wikipedia.org/wiki/Well-ordering_principle), and we refer to the fact when proving another statement.
Structural Induction seems like a kind of Simple Induction / Mathematical Induction to me. It's just that it deals with operations of two elements, so it didn't take too much time to understand.
Structural Induction seems like a kind of Simple Induction / Mathematical Induction to me. It's just that it deals with operations of two elements, so it didn't take too much time to understand.
Subscribe to:
Posts (Atom)