Today was the last day of classes. Danny gave us some topics to review for the exam and we took up a problem on one of the previous exams. The problem was to write a function which returns the head and tail of a doubly-linked list corresponding to an in-order traversal of a binary tree. I wasn't able to find the solution online, so I'll assume I shouldn't post it here. However, the solution was not so dissimilar in structure to this:
def inorder(node):
if not node:
return (None, None)
this = LLNode(node.data)
left_head, left_tail = inorder(node.left)
right_head, right_tail = inorder(node.right)
# do something (i.e. complete links between nodes)
return (left_head, right_tail)
For some reason, I thought that the solution would involve some sort of sandwiching structure. This is what I mean:
inorder()
# do something
inorder()
This is a typical inorder traversal algorithm, so I thought this was necessary to complete the function. Hence, the solution Danny gave seemed like a postorder traversal to me at first glance. After further inspection, I realized that the order of the recursive calls makes absolutely no difference. What does matter is in which order the nodes are linked. I verified this by coding up a preorder function. The function was almost identical in structure to the inorder function, but the node links were slightly different as I expected. It was nice to get this cleared up, since there was a very similar question in one of the labs which I remember I had completed, but I wasn't completely convinced with my solution.
Anyway, that's it for the course. It was great while it lasted.
Good luck on your exams!
Monday 2 December 2013
Friday 29 November 2013
Sorting Algorithms
Last week, we compared various sorting algorithms in our lab. Our results showed that Tim sort was the most efficient sorting algorithm, while quick sort and merge sort were the next fastest followed by insertion sort, selection sort, and bubble sort. For the purpose of this blog post, I will explain the general ideas of selection, quick and merge sort in order to offer an explanation as to why these efficiencies turned out to be the way they are.
Selection sort works by finding the minimum element from position i to the end of the list and then swapping this value with the value at index i. It takes about n - i operations to complete this step. Also, we require that i goes from 0 to n in order to completely sort the list. So the total number of operations will be given by (n + n - 1 + . . . + 2 + 1) = n*(n + 1)/2, which gives us a worst-case time complexity of O(n^2). Unfortunately the best-case time complexity is exactly the same as the worst-case time complexity for selection sort, since we require checking all n - i indices to ensure we have found the minimum value in the list (that means the running time will depend on n^2 even for a list that is already sorted).
Quick sort works by choosing some pivot (simpler implementations simply choose the first index of the list as the pivot), then partitioning the list into two sections: one section is a list containing values less than the pivot value while the other holds values greater than or equal to the pivot value. We sort these two sub lists recursively and then join everything together to get a sorted list. We perform about n operations for each recursive call, and we require about log(n) recursive calls to partition the list until only one element remains. So the average performance is O(n log n). There are cases, however, where this performance is much worse. As an example, consider a perfectly sorted list. Quick sort will choose the first index as the pivot. Since no element is smaller than the first element, one of the sub lists will be empty and the partition essentially does nothing. In this case, we require n recursive calls in order to split the list until one element remains (which means the worst-case time complexity is O(n^2)). A similar case occurs when the list is perfectly unsorted.
Merge sort works by splitting the list in half, sorting each half (recursively) and merging the sorted halves together. This has a similar time complexity as quick sort, we require log(n) recursive calls and perform n operations for each call so we have O(n log n). Unlike quick sort, there are no cases where merge sort behaves poorly. It is essentially guaranteed to run a time complexity of O(n log n).
Our data showed that quick sort runs faster on average. However, on sorted and unsorted data merge sort performed significantly faster (as expected). I would still prefer quick sort over merge sort since the average run time is faster. Also, to address the issues with sorted and unsorted data, we were taught a quick sort variant in Wednesday's lecture which chooses a random pivot. This variant does not have the same disadvantages on sorted data that the original algorithm has. And even though the worst-case complexity is still O(n^2), this is very rare. In fact, the chance that the minimum pivot would be chosen each time is 1/n! and similarly for the maximum pivot. So comparing merge sort and quick sort solely based on their worst-case time complexities is a meaningless comparison in this case. Therefore I claim that quick sort is generally faster than merge sort. Don't take my word for it though, this is simply my opinion based on what we have learned so far. I have noticed varying opinions on several forums about this topic. I am also aware that Tim sort is a hybrid sorting algorithm which uses merge sort. One would question why merge sort was chosen for this algorithm, so perhaps my opinion on this topic will change over time as I gain more knowledge.
Thanks for reading, let me know what you think about quick sort and merge sort in the comments.
Selection sort works by finding the minimum element from position i to the end of the list and then swapping this value with the value at index i. It takes about n - i operations to complete this step. Also, we require that i goes from 0 to n in order to completely sort the list. So the total number of operations will be given by (n + n - 1 + . . . + 2 + 1) = n*(n + 1)/2, which gives us a worst-case time complexity of O(n^2). Unfortunately the best-case time complexity is exactly the same as the worst-case time complexity for selection sort, since we require checking all n - i indices to ensure we have found the minimum value in the list (that means the running time will depend on n^2 even for a list that is already sorted).
Quick sort works by choosing some pivot (simpler implementations simply choose the first index of the list as the pivot), then partitioning the list into two sections: one section is a list containing values less than the pivot value while the other holds values greater than or equal to the pivot value. We sort these two sub lists recursively and then join everything together to get a sorted list. We perform about n operations for each recursive call, and we require about log(n) recursive calls to partition the list until only one element remains. So the average performance is O(n log n). There are cases, however, where this performance is much worse. As an example, consider a perfectly sorted list. Quick sort will choose the first index as the pivot. Since no element is smaller than the first element, one of the sub lists will be empty and the partition essentially does nothing. In this case, we require n recursive calls in order to split the list until one element remains (which means the worst-case time complexity is O(n^2)). A similar case occurs when the list is perfectly unsorted.
Merge sort works by splitting the list in half, sorting each half (recursively) and merging the sorted halves together. This has a similar time complexity as quick sort, we require log(n) recursive calls and perform n operations for each call so we have O(n log n). Unlike quick sort, there are no cases where merge sort behaves poorly. It is essentially guaranteed to run a time complexity of O(n log n).
Our data showed that quick sort runs faster on average. However, on sorted and unsorted data merge sort performed significantly faster (as expected). I would still prefer quick sort over merge sort since the average run time is faster. Also, to address the issues with sorted and unsorted data, we were taught a quick sort variant in Wednesday's lecture which chooses a random pivot. This variant does not have the same disadvantages on sorted data that the original algorithm has. And even though the worst-case complexity is still O(n^2), this is very rare. In fact, the chance that the minimum pivot would be chosen each time is 1/n! and similarly for the maximum pivot. So comparing merge sort and quick sort solely based on their worst-case time complexities is a meaningless comparison in this case. Therefore I claim that quick sort is generally faster than merge sort. Don't take my word for it though, this is simply my opinion based on what we have learned so far. I have noticed varying opinions on several forums about this topic. I am also aware that Tim sort is a hybrid sorting algorithm which uses merge sort. One would question why merge sort was chosen for this algorithm, so perhaps my opinion on this topic will change over time as I gain more knowledge.
Thanks for reading, let me know what you think about quick sort and merge sort in the comments.
Thursday 28 November 2013
Memoization
In yesterday's class, Danny started the lecture by showing us a simple recursive algorithm which returns the nth Fibonacci number. It turns out that this algorithm was horribly inefficient since we were repeating several unnecessary calculations. So within one minute I came up with my own code for the Fibonacci function, here it is:
def fibonacci(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a # alternatively we can return b, if we want to start with 1 instead of 0
This is much quicker than the recursive implementation, it took me about 10 seconds to get the millionth Fibonacci number, while the recursive algorithm struggled with n = 40. During the entire lecture I was waiting for Danny to reproduce this code. Instead, he suggested something called memoization which stores information from previous calculations instead of recomputing them time and time again. So essentially we would store all Fibonacci numbers in some sort of data structure and before computing another number we would firstly check that it has not already been computed to save time. In my opinion, the Fibonacci sequence is not the best example of memoization seeing as the algorithm can be written easily without the need to store things in memory (again, look at the implementation I have presented). I do, however, see the potential advantages of memoization. It is a logical approach to solving a general problem of this form, sacrifice memory space to gain computation speed. Hopefully we'll be doing some more of this in the near future.
def fibonacci(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a # alternatively we can return b, if we want to start with 1 instead of 0
This is much quicker than the recursive implementation, it took me about 10 seconds to get the millionth Fibonacci number, while the recursive algorithm struggled with n = 40. During the entire lecture I was waiting for Danny to reproduce this code. Instead, he suggested something called memoization which stores information from previous calculations instead of recomputing them time and time again. So essentially we would store all Fibonacci numbers in some sort of data structure and before computing another number we would firstly check that it has not already been computed to save time. In my opinion, the Fibonacci sequence is not the best example of memoization seeing as the algorithm can be written easily without the need to store things in memory (again, look at the implementation I have presented). I do, however, see the potential advantages of memoization. It is a logical approach to solving a general problem of this form, sacrifice memory space to gain computation speed. Hopefully we'll be doing some more of this in the near future.
Friday 22 November 2013
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!
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!
Monday 18 November 2013
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.
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.
Wednesday 13 November 2013
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!
"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!
I hope you all did well on your tests, that's all for now!
Subscribe to:
Posts (Atom)