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.

Week 7

This week we continued learning the master theorem, and we also learned a new concept developed by Guass which helps reduce the time complexity of a function. We have been looking at a lot of divide and conquer algorithms which are more complicated to determine the time complexity, but a lot more efficient.

It really helps to have learned these algorithms last year and to know the time complexity for each, because it makes it easier to understand how to solve proofs of equations representing these time complexities. I find these proofs a little tricky since they involve recursion, and I'll need to read more about them or look at examples in the textbook.

One thing I forgot to mention in last week's post is that we received our graded midterms, and as I expected I lost marks on the second question. I'll be sure to be more prepared for the second midterm. Also, I did well on last week's quiz, and I think I did well on this week's quiz as well. This week's quiz was on developing a closed form using unwinding, which I don't have difficulty with.

Week 6

This week we continued learning time complexity and unwinding to develop general equations for time complexity, but with more complicated problems. We applied these concepts to merge sort, and we also learned a new concept; the master theorem.

So far the master theorem is one of my favourite concepts in this course because it allows you to determine the time complexity by plugging in values into a formula, and these values are easy to determine as well. It's times like these when I am extremely grateful for the people who came up with these formulas and short cuts to solving problems, but it also amazes me at the fact that they developed these formulas. I also wonder how they came up with them and how much time it required.

Our quizes from last week were returned this week, and I did well on last week's quiz although I was a bit unsure about the material we learned last week. I spent some time reading about the concepts and now I am more familiar and comfortable with these concepts. I think I did well on this week's quiz as well.

Week 5

This week was short since Thanksgiving was on Monday and we only had one lecture this week since our first term test was on Wednesday. I found the term test relatively easy for the most part, I believe I did well on the first two questions, but I wasn't sure about how to solve the last question so I probably lost marks there.

This week we started learning time complexity for recursive functions. We also learned the concept of unwinding to develop a general formula for the time complexity of a recursive function, and then how to use induction to prove that the formula is correct. I'm having a bit of trouble trying to grasp these concepts, and I've never fully understood the concepts of time complexity in relation to log functions. I'll have to do some more reading about these concepts in the textbook and practice problems.

I feel like this will eventually lead to proofs about constants and breakpoints, which I didn't enjoy too much last year. However, if it does lead to those topics then I'll do the reading and become completely familiar and confident with the material.