Sorts and Big O

If you had a deck of 20 cards numbered from 1-20 laid out in front of you, and you were asked to sort them in increasing order in the most efficient way possible, how would you do it? Surprisingly, there are many acceptable approaches to this problem, which leads to the topic of sorting algorithms. For my last post, I'll be discussing three basic sorts: selection sort, quick sort, and merge sort as well as their efficiency. If any of my explanations are unclear, I really recommend checking out the wikipedia articles on each of the sorts since they are explained in more detail and have gifs which I found really helpful.

       Selection

Selection sort is probably one of the simplest and most intuitive approaches to sorting - you look through the the list (or in this case the deck of cards) to find the smallest element, and put that aside. Then you go through the rest of the deck and continue the process as many times as there were cards you started with and you end up with a sorted deck. In terms of code, a possible implementation is starting at the first (0th) element of an array, and switching it with the smallest value of the rest of the array. Then the second time through you can start on the second (1st) element and so on until you have gone through the array. 

If the size of the input (the number of elements) is n, then the first time through the list you have to check n - 1 elements. The second time, you ignore one element, so you only need to check n - 2 elements, and so on until you have 0 elements to check. So in relation to n, the number of operations you have to do is (n - 1) + (n - 2) + ... + 1 =  (n^2 + n) / 2, which means selection is O(n^2)

    Quick

Quick sort is a naturally recursive algorithm that is as follows: choose an element of  a list that is easily accessible (for example, the first, last or middle one) - this element is called the pivot. Then, move all of the elements that are smaller than the pivot to its left (or right if you want decreasing order) and all of the elements that are bigger than the pivot to its right.  Then, you perform this procedure again to the left half and then the right half (excluding you original pivot, since it is already in the correct position) of the array and repeat until you reach the base case - you have 1 or 0 elements, which don't need to be sorted. The recursive nature of quick sort lends itself to a very simple implementation in code which would look like: return ([quick sort of all the elements less than the pivot] + [the pivot] + [quick sort of all of the elements greater than the pivot]) if the array has more than 1 element, otherwise just return the array.

Assuming that for each pivot you pick, there are roughly the same amount of elements less than the pivot as there are elements greater than the pivot, you'll be splitting the list in half each time, which is logn (base 2). Each time you split the list, you'll be checking (at most) every element against a pivot. Since there are (almost) n elements that are checked logn times, you get O(nlogn).

However, if by chance every time you pick a pivot that is either the smallest or the biggest element in the list you are examining, you'll have to split the list n-1 times. And since the fact that you have to check at most every element against a pivot, the number of operations is roughly n(n-1), which is O(n^2). 

      Merge

Merge is another recursive algorithm which first splits the array until each slice is either 1 or 0 elements or in other words, until each slice is sorted. Then, it goes through all of the sub arrays and merges them into a sorted list by comparing the first element in each subarray and appending the smaller (or bigger if you want decreasing order) element to the merged array until both subarrays are empty (since they are already sorted, the merged array using this method will also be sorted). This process is continued until only one array remains. 

Similarly to the reasoning used for quicksort, since you are performing n operations logn times (for each split), you end up with O(nlogn). 

In the end, it is clear that merge will always be better than selection sort, and quick will almost always be better than selection sort. However, which one between merge and quick is faster? In merge sort you must check every element at every level, whereas for quick sort, you have to check every element except for the pivots that you already know are in the correct location from previous levels. In other words, in the best case, quick sort will have to perform less operations for every split. Since they split their input the same amount of times, a balanced quick sort will be slightly faster. In other words, both of these sorts are composed of two parts: the splitting (logn) and the operations every split (n). Unless the quick sort is perfectly balanced (split exactly in half each time), the splitting part will be somewhere between logn and n, but the operations every split will be less for quick sort. So the faster algorithm depends on the relationship between those two parts, and whether the time lost in quick sort by splitting more times is offset by the time gained in having to do less operations per split. In practice, as we've seen in class, quick sort ends up being slightly faster. 

Week 10 - 12

Looks like we're already at the end of this course. This semester has really flown by! Because of the reading week (or should I say reading days), week 10 just consisted of the second term test. I thought it was pretty straightforward - three recursive functions which test your knowledge on binary trees and linked lists. The one mistake I made was assuming that a default value of None was assigned to the next attribute of a new instance of a linked node. Had I ran my code, I would have realized that the initializer took 3 arguments (self, value, next) instead of just two. I'll have to make sure to pay more attention to the code given in the question next time!

For the past two weeks (week 11 and 12), we touched briefly on a number of different concepts:

• information hiding: 

Here we discussed python's view on the accessibility of attributes in a class and introduced the built in property(), which takes a get, a set, and a delete function as well as an optional docstring and works by setting an attribute equal to the property of any of the above functions. This allows us to vary the accessibility of users - for example, we can create the set function of property() to accept only certain values in order to restrict the possible values a user can change the attribute to. Or, we can input only a get function to property() to make an attribute read only.

• MapReduce:

MapReduce is composed of two parts: it maps a function through an iterable which sorts or filters the values, and then it reduces it to one value. This allows more efficient processing of large data sets by allowing operations to be run in parallel. In order to reinforce our understanding, Danny introduced the reduce() function from the functools module runs a function through an iterable pairwise to reduce it to one value.

• scopes and namespaces

I thought this part was self explanatory, but we went through an example involving local, nonlocal, and global namespaces (using nested functions) to where python checks first when a variable is called - first local, then nonlocal, then global.

• tracing recursive function

Here the main point that Danny made was that when tracing through recursive functions, it isn't necessary to try and go through exactly what the computer is doing. You can first go through the simplest non-recursive case, then afterwards instead of repeating the process, you can just plug in the known results (being a human you don't have to recurse over again to know what the result is) and keep on going until you reach an output.

• memoization

Danny touched briefly on how memoization works and what its benefits are with the classic fibonacci example, and then showed us an example of a memoization decorator.

Overall, I've really enjoyed the course, and I wish everyone best of luck on their exams!

Week 9

Wow, term test 2 is coming up in 5 days already! This past week we talked some more about sorting algorithms (accompanied by some demonstrations by Danny) as well as their performance. We compared the speed of a number of sorts as the input size increased, and surprisingly mergesort was only 3rd, losing out to O(n) sorts like Count Sort and Timsort. Something new I learned was that big O notation was an upper bound for number of calculations as the input increases (rather than just a rough estimate of how it grows), which meant that it had more of a hierarchical relationship: anything that is O(1) is also O(logn), which is also O(n), and so on... This makes more sense after learning about big theta and big omega in CSC165.

Another thing worth mentioning is the lab this week. I must say, they are getting more challenging now! This week the first task consisted of writing a function which took a root node of a BST, and returned the first and last nodes of a linked list consisting of all of the nodes of the BST according to an inorder traversal. My first approach was straightforward: by recycling the code Danny posted on inorder traversal to work on binary trees, you could get a list of all of the values in the BST according to inorder traversal. Then, iterate through the list and to create a linked list with all of the values. Finally, return the first and last nodes of the linked list - simple enough. Alas, after writing this out in code I realized that I had missed a crucial detail - the function must create and link the linked list nodes as it visits each node inorder in the tree, making things a bit more complicated.

Using a hint from the TA ("think about joining two linked lists that are already in the correct order"), I came up with a new approach: take inorder linked list of the left subtree, join it to the linked list node instance of the root node, and join that to the inorder linked list of the right subtree. However, the more difficult part was actually writing the code. Although I eventually managed, all of the conditionals along with the helper function ended up being around 20 lines, much more than the dozen that Danny suggested would be optimal. The second part of the lab consisted of writing a function which would return the head of a linked list containing the nodes from the longest path in the binary tree. My current approach is to have the function work recursively by having the linked list node instance of the root point to the max of the longest linked list for the left subtree and the longest linked list of the right subtree. Easier said than done! It was difficult to think about recursion with linked lists since one can only modify a linked list by changing the pointer (in this case an attribute of the node) of the tail of the linked list, and then recursively calling the head of the linked list. I found it helped to write out the function in pseudocode first, using pen and paper and diagrams if needed, and then gradually working the necessary bits of the function part by part.

I didn't have the opportunity to finish the second part of the lab, but I'll keep working on it this weekend, and ask at the CS help centre if I get stuck, and hopefully come up with a nice solution for the lab.

Week 8

This week, we continued on and talked about binary search trees and touched on big o notation/some running time analysis (which we are learning concurrently in CSC165) as well. I'll be discussing mainly BSTs and the assignment which is due next week.

In essence a binary search tree is a binary tree where the left subtree of a node only contains values smaller than the value of the node, and the right subtree of an doe only contains values greater than the value of the node. This allows for a quicker search (roughly O(logn)) for most cases. Earlier in the course we encountered a data structure very similar to BSTs (I forget if it was a lab or an exercise) which was essentially implemented as a nested list instead of a tree. In both cases they essentially provided a different kind of structure to perform binary search (as opposed to the standard way on a sorted list). Instead of finding the midpoint in a list, and changing the upper and lower bound every iteration, in a BST the root is in a way the midpoint, and you traverse to the left subtree or right subtree instead of rerunning the algorithm on the left half or right half of the list. It isn't clear to me the benefit of implementing a binary search tree instead of sorting a bunch of values in a list, especially since binary search on a list will always be O(logn) whereas the BST could have a worst case runtime of O(n) if every node only has a right child. Perhaps the different variations of BSTs that Danny mentioned in class (AVL, red-black, splay, tango trees) have a better performance in more specific situations.

While going over BSTs, we also covered some of the common methods of a BST, like inserting, deleting, and the __contains__ method. They are both simpler than I expected, and involve finding the location of the node in question (or where it should be), and updating the children of the nodes around it to either delete or insert a node (I'm oversimplifying it a little). The contains method was the easiest of all, but is an extremely useful method to have, especially in a class like a BST. In the last few classes I learned a lot about useful built in methods like contains, len, repr, and str. One thing that I didn't realize was that with the insert method, the initialization of a BST with a list of values was made much simpler by just calling the insert method on each value.

A last thing that we did this week was finish up on assignment 2. I had never thought of organizing regular expressions into a binary tree, but it did seem an extremely natural thing to do. The assignment was a great way to practice recursion and manipulating/using binary trees while learning about what a regular expression is. It also provided some review on classes and inheritance. After this assignment I realized that so far the assignments have been very helpful in allowing the opportunity for the application of the topics learned in class on a larger scale and in a more challenging way than what is done in exercises and labs.

Speaking of which, if anyone was able to finish the iterative function of count_less from the lab let me know how you did it!

Week 7

This week we covered something I've been looking forward to for a while - linked lists. It seems a lot simpler after learning about it but there were lots of things to take away from the course this week.

There are two ways of thinking about the linked list, both of which can be summarized in one sentence: either as a sequence of nodes, each of which contains both a value and and an embedded reference/link to the following node in the sequence, or as a tree with an arity of 1. It seems simple enough, but the wording made it a bit confusing to me. In class, the nodes were represented as classes with a value/item attribute, and a next attribute (the link), which was itself a node. In that case, it seems like the nodes in a linked list do not contain references to other nodes but rather just contain the nodes themselves as an attribute. This seems to be contradictory to the picture used to represent linked lists:

which looks like a sequence of nodes. Rather, the code makes the link list seem like a bunch of nested nodes, with the depth as an indicator of the order. Thinking about linked lists this way, or as a tree, makes more sense to me.

Another difficulty I encountered this week was understanding the difference between __repr__ and __str__. In essence, although they are both string representations of an object, __repr__ is called when either the object itself  is called or repr() is called on the object, and __str__ is called when print() is called on the object. The main difference is that __repr__ is a more formal representation of the object, and should return enough information to be able to fully reconstruct the object. In other words object == eval(repr(object)) should return true (although in practice this doesn't always happen because sometimes it leads to an infinite loop). On the other hand, __str__ is more of an informal representation and emphasizes readability rather than unambiguity.

Besides these two concepts, we covered some other methods like __contains__, __len__, and __getitem__ (which we were also able to try and implement ourselves in the lab) which allowed us to get some more practice writing recursive methods for trees.

Also, the links to all of the SLOGs were posted this week so I'll be reading over some of them and talking about what some of the other students are thinking in the remaining weeks. I'll try to comment on things I find interesting and hopefully others will comment on this blog if they feel like it. Overall, I really enjoyed the class this week and was able to learn some new concepts while applying them and practicing older ones.

Week 6

Week 6 - the halfway point for the course! Coincidentally, because of Thanksgiving and the first midterm we didn't have any class for the week - just the midterm on Wednesday and lab #5/ exercise #4 on Friday. 

First off, let's talk about the midterm. It was a fair test, and covered recursion, classes/inheritance, and testing. I liked that the questions were varied as opposed to being along the lines of: 'write code for this function' each time, testing our understanding in different ways. I thought that the first question was interesting - it involved calculating the output for inputs 1-6 in the recursive function we had to write for assignment 1.  I thought that it was a good way to test the ability to read and understand how a recursive function works - except for the fact that those who went far enough in assignment 1 have already written the exact same function themselves, and that more time was spent doing simple arithmetic than thinking about the code. The rest of the questions were quite straightforward: writing a recursive function, implementing a subclass of list, and writing 3 possible tests to test our subclass. Overall, I enjoyed writing the first midterm.

The exercise this week was about tree traversal, and was a good way to keep the concept of trees fresh in our mind in preparation for linked lists the following week. Since we only touched on trees rather quickly during week 5, it was a good opportunity to review the code for the different tree traversals, as well as get some practice writing recursive functions for trees.

The lab provided a good comparison of the efficiency of three different ways of iterating: for loops, list comprehensions, and generators. I remember when I first started learning Python that one of the first problem sets involved a problem very similar to the pythagorean triples function in the lab. It was a struggle back then, but I never realized how simple the solution could be with list comprehensions/generators. Finally, one last thing I learned this week was the any() built in function - something I wish I knew about sooner!

Next week we'll be covering some new and important material (link lists) so I'm looking forward to that next.

OOP and recursion

The assigned topics for this week that I'll be talking about are Object-Oriented Programming, and recursion. These two words pop up pretty often in the programming world but what exactly are they and why do we care?

Object-Oriented Programming, or OOP for short, is a programming model where everything can be represented as an object or a class. What is an object/class you say? Well in truth it can really be whatever you want it to be.

For example, in Python a string is an object. In this case, it's a sequence of characters which have certain characteristics or "attributes", like their length and also certain functions or "methods" that can be applied to it, like the join() method. At first the purpose of OOP may not be obvious, but the main benefit is that it allows us to abstract physical things and concepts that we have in the real world, and create a recipe for it in a program. Using the previous example, a string is really just a recipe for representing some text. An instance of a class, for example of a string, is a specific example of that class. Something like 'hello' would be an example of a piece of text, or using OOP lingo, an instance of a string.

Another benefit of OOP is the concept of hierarchy, which is a very human and natural way to classify things. For example, let's say there is a zookeeper who wants to represent his zoo in the virtual world. He would like to be able to classify the animals in his zoo, but also store attributes (what's their name, what do they eat, how many legs do they have) and methods (feed the animal, clean up their enclosure) related to each animal. A natural way to approach this would be to create a class (a specific object) called Mammals, which could have an "number of legs" attribute of 4. Then, he could create a subclass of mammals called lemurs, which would have a "food" attribute of bamboo. Finally if he had a lemur in his zoo called George, he would create an instance of a lemur with the name "George". In OOP, a subclass inherits from its superclass, which is what allows for this kind of organization.

In short, OOP allows programmers to abstract ideas from the real world and represent them in a program, whether it be plain text, animals, or stacks.

Another concept which allows programmers to bring real world thinking into a program, is the concept of recursion. Recursion is essentially the idea of breaking a task down into smaller bits, until the pieces of the task are small enough to be solved very easily, and then finding the solution by rebuilding all the solved pieces together. In a function, this manifests itself as having a base case, the smallest possible piece, and having the function call itself on a smaller piece until it gets to the base case, which is when it starts building back up. An example of a recursive function would be a function that calculates the nth fibonacci number. If you were asked to calculated the first or second fibonacci number, the answer would be simple: 0 or 1, because you already know what they were. However, if you were asked to calculate the third fibonacci number, then you would have to think back: what was the first and second number? Or, for the eighth fibonacci number, you would have to think: what are the sixth and seventh numbers? To solve that, you would need to find the fourth and fifth, and then the second and third, and so on. Hence, recursion is in fact a very natural way to think about solving certain problems, and usually leads to very readable, simple, code which can solve seemingly much more complex problems.

Using these two concepts of OOP and recursion, computer scientists are able to bring more natural concepts and ways of thinking from the real world into a program.