Week 11 of CSC148: Sorting and Efficiency

Here we are, the last of the mandatory SLOG posts and the last week of CSC148 as a whole. Today, I'll be sharing a little summary of what I have learnt so far about sorting and the efficiency of algorithms.

Sorting is something I became quite familiar with in CSC108. In both this course and the latter, sorting has commonly referred to organizing a list of n amount of integers from smallest to largest. For example, an unsorted list of n = 5 elements may looks like this: [2, 3, 4, 1, 5], which after running through the sorting algorithm would come out looking nice and sorted like this [1, 2, 3, 4, 5]. There's a plethora of sorting algorithms that have been created to handle this seemingly simple task and each one of them uses a different (or at least a variation on pre-existing) method. Bubble sort, for example, goes through each element of the list and compares it to the element to its right. If this element is smaller, both elements switch places. This algorithm keeps 'passing' over the list until every element is sorted. Another sorting algorithm, insertion sort, works by creating a sub-list starting from the beginning of the list and "inserting" each new value into its proper spot until the len(n) == len(sublist).

I remember asking myself the following question when first encountering sorting algorithms: if the task is always the same, why are there so many sorting algorithms? Well, put bluntly the task is not always the same. Every sorting algorithm has its strengths and weaknesses, some are just plain slow, and some are just plain fast. Timsort for example, as we saw in the lab last week is blazing fast in virtually every case, there's little wonder it is the default Python list sorting built-in. This is where efficiency comes in. On a small n, efficiency is of little concern. But when n increases to larger and larger values, which it tends to do in CS, especially when dealing with large amounts of data, efficiency becomes a critical concern. In CSC148, algorithm efficiency is commonly analysed on a worst-case basis. That is, the situation where the list is organized in a way that exposes any conspicuous inefficiencies in the algorithm. Big-oh notation is also used, which is the upper bound on the growth rate of the function ignoring any constants (i.e. 3n^2 is O(n^2). For example, a few weeks ago Danny was showing us Quicksort lecture. In the typical case it was quite fast, with O(n log n), but when run on an already sorted list, efficiency dropped to an abysmal O(n^2), which is the worst case for Quicksort. Any runtime near O(log n) is quite fast, n is being halved every time the algorithm makes a pass meaning even massive values of n are reduced quite quickly. On the other end of the spectrum, O(n) is quite a poor runtime, which also happens to be the runtime of bubble sort because, as the algorithm was described, it must look at every item in the list even in its best case. 1,000,000 items would require 1,000,000 times the amount of time as when n = 1--ouch!

The amount of time required for a function run one time is also an important factor in efficiency since this is the number that is multiplied by the big-oh runtime to calculate how long it will take a function to serve a specific purpose on a specific machine. To maximize efficiency in this regard, it is important to observe that there are no redundancies at any step within the code. To bring up another example from the lab, a decrease in runtime was noted when storing the length of n in a variable rather than calling len(n) multiple times within a loop. Given that both processor speed and time are valuable resources, efficiency is indeed an important aspect of algorithm design in programming.

Hope you enjoyed this post on sorting and efficiency!

Week 10 of CSC148: Assignment 2 Part 2, LinkedLists

Well, it's hard to believe we are already at the second last week of CSC148. I remember the first post on this SLOG as if it was yesterday...

The majority of my week 10 was spent on the second part of assignment 2 and, overall, I felt it was a very useful assignment to have done. I felt like I had both solidified my skills with writing recursive functions as well as my understanding of tree abstract data types. After all, the special regex trees we were working with were basically just binary trees with a bunch of added restrictions.

All four of the functions (and in my case, an added helper function) covered one aspect of regex tree ADT: building them, breaking them back down, and checking their validity. Of course, not every part of the assignment explicitly had us working with the regex tree ADT, but a big part of the assignment forced us to view a regex expression string like '(1.0)*' as a tree-type data structure in itself.

I felt the biggest challenge with the assignment was the regex_match function in particular. Not because it was particularly difficult to write, but more so because it had so many different "moving parts". This is the first big function in CSC148 that I've had to write that I felt it necessary to test over and over again to see if I had every little outlier case working...and with good reason too! It was tedious but testing this function vigorously would, not often but every little while, produce some kind of tiny error in the "moving parts" that had to be tweaked. Working on this function gave me a really good first hand look at the importance of testing to writing code.

Another thing that's been floating around in my mind, and not just because it has to be due to test 2, are LinkedLists. They are seemingly simple at first glance, and appropriately so, since they are much simpler that trees in terms of their structure, but implementing them with other ADTs has been a little bit of a hassle in the tutorials so far. So for the next week, LinkedLists will be a big priority for me.

Hope you enjoyed this post!

Week 9 of CSC148: BSTs, Runtime, Efficiency, and Exercise 3

So it seems this was the final week on tree data types as we transitioned from binary search trees into runtime and efficiency of algorithms, and ultimately the idea of big-oh, which I'll save for another week once we've done more work on it. Binary search trees, although a new concept, was more of a modification on something that I understood well at this point, and if anything, was a simplification of these concepts. The idea is that for every parent and its children, the left sub-tree must contain a smaller value than the integer value of the parent while the right sub-tree had to a have larger value. This is an expansion of something that was taught in CSC108, and actually made the concept a lot clearer for me. I believe the main thing to take a way from this ADT is that every time the algorithm is run, the size of the pool of possible values is cut in half. Contrast this to a regular Tree ADT, one where there is an integer at every node without the restriction on the left and right children. In this case, the algorithm must search the entire tree in the worst case, a linear runtime. And as we learnt, linear runtime is not a runtime you want to be dealing with! 

As for E3, I had a little bit of difficulty with the functions we had to write but in the end I was very happy we were tested on this material. Being forced to grind out some work on recursion really helped me get to a point where I now feel very comfortable with recursion. I finished the exercise fairly quickly with some clunky code but decided to use recursion to its full potential and I ended up with some clean code I was very proud of. A big part of this was remembering a little aid I had read somewhere for writing recursive functions, I believe it was in the readings for the intro week on recursion. The trick is to start writing a function for every possible size of the input. So, start with the base case, of course. Then go on to writing a function that deals with the case where there are two of whatever you're dealing with, and so on. Hope that tip helps anyone that may be reading!

Now on to the second part of assignment 2...

Week 8 of CSC148: Assignment 2, LinkedLists, and Other Recursive ADTs

If I had to pick one word to summarize the last few weeks of CSC148 I would, without a doubt, pick the word "trees". All of the recent labs, assignments, exercises (E3 was just posted and, from a quick glance, looks like it involves tree traversals), and lectures have had to do with trees or some tree-related data structure, or more specific, nested ADTs like LinkedLists. Therefore, it seems only fitting to discuss the topic a little bit this week. Since linked lists are essentially just trees with an arity of one at every "branch" the same realm of logic applies throughout.

An important part of understand trees (or Trees, to be more accurate as were talking about a Python class), is understand tree traversals. There is pre-order, in-order, and post-order traversal, 3 algorithms which involve "visiting" the node before "moving" left then right, visiting it after going left but before going right, or visiting it after going both left and right, respectively. In exercise three we are required to take a in-order and pre-order traversal list and produce the corresponding tree, which is what I'm starting to think about now.

A part I have found interesting about nested structures while working with them so far is that their methods are often much more simple and elegant than you think their implementation might be like at first glance. I experienced this head-on in the last lab where we were required to write a few functions for the LinkedList ADT. My partner Brian (check out his great SLOG here) and I had gone the iterative route when designing our functions, only to realize later that our clunky code was much longer and more complicated than the recursive alternative to tackling the problem. It was definitely a good lesson, though. Another thing we realized, and something I had noticed on the assignment 2, was that often-times when dealing with linked structures like Trees (whether binary or not) you can find yourself writing recursive functions without even realizing. For example, if you write an __eq__ method for a Tree class, one option is writing it out as so:

return (self.value == other.value) and (self.child == other.child)

I hadn't noticed it at first, but by writing out this method I had written a recursive function. Since in many cases the child may be another Tree, the __eq__ will call itself again, and this will continue all the way until child refers to None in both. I found this very interesting.

Back to finishing up assignment 2 and time to start exercise 3!