Week 10 - Sorting

Well this was a pretty hectic week! Let’s start off with what happened in lectures.

A lot of lecture time was spent going over Assignment 2 and a few tips on how to get certain functions working. I found this really helpful since it gave me a better idea on how to code regex buil_regex for example. It also helped with understanding what our base cases should be, which was pretty important since most of our functions were recursive.

After a lot of thinking, coding, improving (and repeating this cycle) we finally got A2 Part 2 done. It was definitely a pretty interesting assignment, and challenging, but we got it done! The main function we had trouble with was is_regex() since there were so many different cases we needed to keep in mind. build_regex also caused a few problems, thankfully, my partner and I managed to figure out a way to get it working!

But this week’s lecture was pretty interesting! We mainly went over different sorting functions, are two main focuses being quick sort and merge sort, and the difference in their runtime. When we learnt about merge sort, I understood it pretty quickly, since it basically involved splitting the list in half and sorting those lists, by splitting them in half again (RECURSION ALERT). This picture basically describes how it works:

Since this function is splitting the list in half multiple times, this gives it a runtime of O(nlogn).

Then there’s Quick Sort.

At first, it took me a while to understand the whole concept of the pivot and how it worked. However, this picture explained quick sort pretty well:

In short, this function picks a random pivot and sorts the list on either side of it. I thought that Anish (http://www.anishslog.blogspot.ca/) explained it pretty well, and his post helped me understand why the runtime of this sort was O(nlogn), which is since the pivot is chosen logn times and there are n items in thse list.

Lab 9

I found this week’s lab quite easy, since it was on binary tree and it was very similar to our exercise. For the first part, we had to code a function that would find the inorder traversal of a binary tree using LinkedLists. After a bit of drawing out how our function should work, and of course recursion, we managed to get the function working. The second part was to create a function that produced a LinkedList version of the longest path in the binary tree. This was almost identical to Exercise 3 where we had to make a function sum_to_deepest, so my partner and I made a function similar to that and then instead of adding the values, we just made sure they were printed.

That’s all for this week! Good luck on Term test 2 everyone!