Week 11

The semester is almost over! Our last assignment is due next week and we only have 1 more full week of class left. It's amazing how fast time flies when every week is so busy with assignments, quizzes and tests, and lots of studying. The second semester will probably fly by just as quickly, and then I'll already be done half of my undergraduate education. I still feel like I just started university last month.

This week's quiz was about determining FSAs given a language. I find this is a very systematic approach, which is nice because the method to solving the problem is the same for every problem. These kinds of problems can become tedious and repetitive, but they are also fairly easy.

We learned regular expressions and NFSAs this week. Regular expressions, which conveniently we are also studying in CSC207 at the moment, are a way to represent languages and the strings that are accepted by a language. NFSAs are similar to FSAs except that they are non-deterministic. The previous FSAs that we looked at were DFSAs, which are deterministic finite state automatons, where each state can only have 2 transitions for binary strings; the transition of a single digit 1, and a single digit 0. NFSAs differ in the sense that every state can have multiple transitions; it can have multiple transitions for the digit 1, multiple transitions for the digit 0, and even a transition for the empty string ε. So far, I find these concepts fairly easy to understand, and it really helps that we learned regular expressions in CSC207 recently. 

Also, regarding the problem solving question, we are required to use G. Polya's approach to sovling the problem. I know that some students have written algorithms or programs to help them solve the problem, but I think that this problem can be solved without them, and that is the approach I will take. 

Week 10

This week was another short week since we had Monday and Tuesday off as part of our reading "week". I find it ironic that our reading week for first semester is only 2 days, but to be fair it is called a break by the university rather than a week. So, since we did not have school on Monday, we also didn't have a quiz this week, and we didn't get our quizzes from last week returned.

This week we learned formal languages and FSAs, also known as Finite State Automatons. FSAs represent "machines" that accept a certain "language". I use quotation marks here because these names represent things other than what they usually represent. A language accepts only a certain set of strings, so we are dealing with sets and subsets once again. Having lots of experience with sets and properties of sets in the past from last year's course, CSC165, and this year's course statistics course, STA247, I feel comfortable with this material and I think I am grasping it fairly well from the very beginning.

I also find FSAs are very logical and systematic in the way that you draw them and analyze them. It is fairly easy if you approach each problem involving an FSA by taking it step by step, either through the the strings that a language accepts, or through the FSA to determine a language that it represents. Another new concept we learned this week was transition functions, which I will have to read some more about because I have to admit, I did not pay complete attention in lecture when this was taught.

Week 9

I wasn't here this week for the midterm on Monday, so I wrote the midterm on Thursday instead. The midterm was not what I expected whatsoever, and I was not prepared for the material that it covered. Since I wrote the evening section's midterm, I expected the evening section to cover similar material as the morning section at the same pace, however, the midterm covered material that was ahead of what the day section midterm was supposed to cover. So once again, I don't think I will do too well on this midterm.

The reason I missed class was because I flew out to Seattle to due several interviews for a summer internship. I got the internship so now I have no regrets about missing class. I also missed lecture on Friday, and when I look over the notes from the day section's class, they were not very descriptive. So I think I'm going to study the evening section's notes for this week.

This week we learned proving partial correctness of an algorithm that determines an nth power of an integer. Really all that this involves is proving the loop invariant, but in most cases we must determine this loop invariant by tracing through the algorithm and noticing what is consistent at the end of every iteration of the loop in the algorithm.

I also look at the problems that Professor Heap posted on his problem solving wiki, and I think I will solve the Penny Piles problem. Here is the problem:

You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:

L

If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.

R

If the right pile has an even number of pennies  transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

What about arranging things so that one of the piles has other numbers in the range [0,64]? What about starting with a different number of pennies in the left drawer?

You may record your problem-solving excursion below the horizontal line.

My intuition tells me that it is impossible to achieve odd numbers of pennies in either drawer, except for 1 penny in one drawer and 63 pennies in the other, since 64 is a power of 2 and you can only divide by 2 if the drawer contains an even number of pennies. I will think some more about this problem, and I will start the problem-solving excursion this week. 

Week 8

This week we started one of my favourite concepts from last year; proving correctness of algorithms! It involves proving preconditions, loop invariants, post-conditions, and termination for different algorithms, and this week we did binary search. We learned how to prove these for both iterative and recursive binary search algorithms, and once again, recursive is more complicated than iterative.

Also, our second assignment was due this week, and I know I didn't do as well on this one because after I submitted the assignment, I learned that we were not supposed to use the master theorem to answer the last question. I thought the question was rather easy if we used master theorem to prove it, but at the same time I don't see reason to learn a concept if we can't use it in the course. I guess since the master theorem is a shortcut, it is considered "cheating" to use it in certain proofs.

This week's quiz involved the master theorem, so I found it fairly easy. I lost marks on last week's quiz since I made some mistakes. I need to be more careful in avoiding making silly mistakes that cost me marks. I should also start working on the problem we're supposed to solve as part of this slog assignment.