Assignment Two and Test Two Results

In a previous blog post, I was discussing a test case error I had in my second assignment. Someone was kind enough to post some test cases for me to try out with the star node. I tried them out and passed all of them. When the results arrived on MarkUs, I was finally able to see the test suite and find exactly where I went wrong. Here was my code for the star node:

if r.symbol == '*':
     return s == '' or any(root_match(r.children[0], s[:i]) and
                                     root_match(r, s[i:]) for i in range(len(s) + 1))

The code failed on regex_match(RegexTree('e*'), '0'), it produces an infinite loop in this case. The key here is the splicing index. My method calls itself with the same string and same regextree, which indeed produces a stack overflow of recursive calls. After investigating, I found the correct code to be:

if r.symbol == '*':
     return s == '' or any(root_match(r.children[0], s[:i]) and
                                     root_match(r, s[i:]) for i in range(1, len(s) + 1))

That's right. The code is nearly identical except the index starts at one instead of zero. Ouch. Since my code worked on more complex test cases I naturally assumed that it would work on simpler cases. This goes to show that you should always check simpler cases in your own code and make sure they work perfectly.

On the bright side, I managed to ace the last test for my first 100% on a midterm at U of T. Hopefully there will be many more to come. I hope everyone is enjoying the course and I wish everyone the best of luck in their course work. Cheers!

Python's "Private" Attributes

Today we learned something interesting in class. Apparently Python does not make use of private variables like C++ or Java does. This was a little bit unsettling to hear, since I've mostly programmed in Java and can't imagine the security risks and other problems that might arise as a result of this fact. For example, say the user is fiddling with class variables which he/she has no reason to fiddle with. Well, Danny showed us a neat solution which the creators of Python use to fix this issue. The solution is to use the built-in "property" method. I'd rather not get into the specific syntax of all of this. I would, however, like to discuss the main idea of this method and how it fixes the problem (who wants to read syntax in a blog post anyway?). Here's how we do it.

We want to define getter and setter methods just like we do in Java. However, we don't necessarily want people to use them explicitly in their code. So when a private variable is referred to in our code, we want our property method to implicitly call the appropriate class methods to do the intended work for us. To make this more clear, let's say a programmer refers to a private variable in our class and assigns a value to it. The programmer does not need to call the setter method explicitly, instead the property method would probably recognize the equal sign used for assignment and it would determine that the setter method we defined in the class would be appropriate in this case. Suppose the programmer chooses not to assign it a value, but rather uses it for output or to calculate some intermediate result. Then our property method would again search for the appropriate class method to use and it would choose the getter method in this case. The advantage in this is that we can customize our getter and setter methods so that we can enforce certain rules. For example, if the user assigns some non-nonsensical value to a private variable then we should throw an exception in this case. This is the main idea of the property method explained today in class. This is almost equivalent to information hiding in Java, so it solves this problem (although it still doesn't really enforce privacy of variables).

Now this is great and all, but something else concerns me. In Java we have private classes which are inaccessible from another class. How could such a thing not exist in Python? Well we've already learned a way to fix the issue of private variables, so perhaps there is a solution to this problem as well. I guess we shall see in the coming weeks.

Second Assignment Automarker

I recently looked at the auto marker results for assignment number two. If the mark for the assignment is given solely for the number of test cases passed, then I would be pleased seeing as I passed all but one. But for some reason, I cannot figure out why I failed this one test case. The error message is as follows:

"ERROR: Test case: regex star of leaf correctly renounces string? ERROR: RuntimeError
maximum recursion depth exceeded in comparison"

Unfortunately I have no idea what this means. My code seems to have no flaws in it (but then again you can never be too sure) so I'm very curious as to why this test case failed. Also, it seems unlikely that my code would fail only one test case. If my logic would have been even slightly off, then this would have likely resulted in several errors rather than just one. Conversely, if my logic was spot on then I should have no errors unless there was a very very small detail which I somehow missed. Anyway, I'll talk to Danny about this error and hopefully gain some insight as to why this happened, or perhaps someone can give an explanation as to why this error occurred in the comments.

Cheers!

CSC148 Second Test

I wrote the second term test earlier today. I must say I liked it very much. The test consisted of three questions involving tree structures where we were expected to write a recursive method for each. In my opinion, a test where all the questions involve recursion can sometimes be very confusing seeing as there are two possibilities when writing a recursive function: either get the algorithm correct in five to ten minutes, or spend hours trying to find the solution (there is usually no in-between). The latter happens to me sometimes when I try to present an overly extravagant solution instead of keeping it simple. Regardless, I still like recursive problems as they induce thinking. Also, this time around the problems were very straightforward and closely related to the exercises and labs done in class. On top of that, the solutions to the problems were less than five lines long (with the exception of question one). I thought the first question was probably the most difficult. The reason I have this opinion is because two base cases were required to complete the function as opposed to just one. In addition, you have to work with a tuple as the return value instead of a single value, which is slightly more complicated. Nevertheless, I was able to complete the question fairly quickly along with the other two.

I hope you all did well on your tests, that's all for now!

Big-O Notation

We covered big-O notation in class over the past couple of weeks. There are a few things which struck me as interesting. Each function belongs to a set of functions with the same run-time performance. For example, a linear search will belong to the set of functions with O(n) performance whereas a binary search will have O(log n) performance. But technically, big-O is an upper bound on an algorithm's performance. In other words, all of these sets fit into a hierarchy. So O(log n) is a subset of functions with O(n) performance (since functions with O(log n) performance cannot possibly do worse than an O(n) function). Similarly, O(n) is a subset of functions with O(n*log n) performance. So technically, a binary search algorithm fits under O(log n), but it also fits under O(n) and O(n*log n). This is what I found somewhat strange. Can I claim every algorithm given on the upcoming midterm is O(n!) and get full marks? This seems absurd.

To address this, I would assume an algorithm is classified by its simplest performance. In other words, we say linear search is O(n) and not O(n!). I don't think this was directly mentioned in class, but it seems to be a reasonable assumption to make. This was later verified in my CSC165 lecture. Hopefully the material covered in my CSC165 class will help with big-O questions on the midterm, and maybe the material covered in CSC148 will also help with my CSC165 class (awesome timing)!

Anyway, good luck on your upcoming midterms!

Second Assignment

The second assignment was due today. Fortunately, I was able to finish it several days ago. The first part of the assignment was fairly straight forward. The main challenge in this part was being able to recognize which node is the root node in a regular expression. As a human, one can immediately determine if a node is the root by checking how deep it is in the expression. Using this same logic, I kept track of the expression depth by having a running counter and adding one whenever a left bracket is reached, and also subtracting one whenever a right bracket is reached. This would be useful when checking if a node is the root (i.e. if the count is equal to one, then the node is found in the lowest depth of the expression and must be the root). This is the first approach that came to my mind. I am curious if there are others which people have implemented. Let me know in the comments.

I found the second part more challenging. The main challenge in this part (for me at least) was handling expressions with star nodes. This involved splitting up a string into several combinations of sub strings and checking that each sub string matches the RegexTree for at least one of those combinations. After spending quite some time trying to do this with loops, I was able to gain some helpful insight from Danny in lecture. For anyone who is stuck on this part, I strongly recommend following his advice and using recursion.

On an unrelated note, I mentioned a problem I had on the first test in my second blog post. After reviewing the solutions, I noticed that the __init__ method in question three was completely omitted from the class we were meant to implement. This makes much more sense, so that clears up my confusion I had for that question.

Anyway, good luck on your second assignments!

Last Exercise

So the last exercise was due Friday. Having no time to start on it until Thursday (the day after my physics midterm), I was rushing to get it done. When I actually looked at the exercise I immediately realized it was painfully easy (in fact most of part (a) had already been done for us in the insert method). I was relieved and quickly finished both parts of the exercise within 5-10 minutes. I then submitted the exercise to MarkUs. Feeling confident the next morning, I decided to check my results. All of part (a) was done perfectly, whereas part (b) had 9 errors. Huh? Well apparently the method in part (b) should return the node with the maximum value and not the value itself. The handout made this very clear, but for some reason I decided to completely disregard it anyway. I spent a good 10 minutes trying to figure out what was wrong with my code only to find that there was almost nothing wrong. I quickly changed the return value and submitted to MarkUs once more to get a perfect score. It's somewhat relieving to know that I don't need to stress out every week to finish these small exercises anymore (they are usually quite easy, but even the easiest of assignments can be rather stressful). Then again, these exercises do provide an opportunity to raise one's mark. I also find it kept me on top of course material since it forced me to refresh my memory on what we're doing each week. Well, I guess that's it for the CSC148 exercises. So long!