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.