Week 11: Sorting and Efficiency

Sorting is something intuitive for most people, we make quick comparisons to decide the placement of an item and sometimes even identify the largest (or smallest) items and put them in the "right" spot. Computers are most certainly more efficient than the average human mind when it comes to sorting very large arrays, but it's not intuitive - they need more specific, systematic instructions. However, some "instructions" (sorting algorithms) are certainly more efficient than others.

Some of the sorts we've encountered are:

•  selection sort - find the smallest item in the unsorted portion of the array and place it in its final spot
•  insertion sort - go through the list item by item, placing each item into its right spot relative to the already sorted items
•  bubblesort - go through the list comparing and swapping adjacent items as needed and repeatedly do this until the list is sorted 
• quicksort - choose a pivot and split the list into two; items smaller than the pivot (left) and items larger than the pivot (right) and then recursively call quicksort on both and then join the sorted left, pivot and sorted right.
• mergesort - split the list into two, sort each and then merge the two sorted lists

Generally, the first three tend to take the longest run time on lists which we can see by looking at the methods that are employed. For example, bubblesort looks at each item in the list multiple times before the entire array is sorted. So it's believable that bubblesort has O(n²) time. (Imagine how long that takes for n large!) The last two employ "divide and conquer" methods which are much more efficient when sorting. Mergesort and quicksort have O(nlogn) run time (the exception is the worst case of quicksort which has O(n²) time) which is much faster than O(n²) time. So quicksort and mergesort are much more efficient!

An interesting point to note, the built-in sort used by Python employs many different types of sorts, depending on the size of the array passed in, which is why it is faster than all of the sorts mentioned above - it makes use of all the benefits offered by various sorting algorithms!

Week 10: Something doesn't match up...

This week the second part of A2 was due, which involved 4 functions; is_regex, all_regex_permutations, regex_match and build_regex_tree. The first hill to get over was is_regex, since my thought process would use it in all_regex_permutations and use a very similar method for build_regex_tree.

However, regex_match gave me a lot to think about...and somewhat of a headache. No matter what I did or how I thought of approaching the problem, I couldn't figure out how to write the code so that it did what it was supposed to do in all cases. In the end, I submitted code that didn't work in (as far as I checked) one case, so hopefully I'll still do well. Turns out a classmate of mine had the opposite problem as me so we'll both have a look at each other's code to figure out our problems before the midterm on Wednesday.

Until next time, good luck!

Week 9: One big oh!

This week we did work on Binary Search Trees (BSTs) and in particular looked at deletion of data from BSTs during lecture. We also started learning about algorithm performance and analyzing the running time of an algorithm in terms of the size of the input n. We looked at the worst case scenarios of sorting algorithms and found that binary search is almost always more efficient than linear search which is pretty cool.

The idea of the big-oh notation is to give an upper bound on the worst case running time of an algorithm. For example, O(n) means that the algorithm's performance is directly proportional to the size of the input passed to it. Similarly, O(n²) means that the algorithm's performance is proportional to the size of the input squared. Since the big-oh is an upper bound, we can see that we can write things like O(n) ⊆ O(n²). That is, the run time of algorithms that are proportional to the size of the input will most certainly be less than (or bounded above by) the run time of algorithms that are proportional to square of the size of the input. In theory, the idea of an upper bound was easy for me to grasp but understanding it on an example is definitely something I have to spend some time on.

A2 part deux is due this week, so time to get to finishing it. Until next time, adieu!

Week 8: Inherit this!

This week I chose to write about the first part of A2...the regex trees.

To be honest, the first time I sat down to do some coding, I was barely making use of having a superclass even though I knew that the assignment was on inheritance. It took me 3 or 4 instances of copy-pasting chunks of code and only making minor changes to them before I finally stopped trying to plough on through the assignment. Even though I conceptually understood the importance and usefulness of inheritance in creating classes, I wasn't applying it. My code would have most certainly worked, I have no doubt, but then what would have been the point of learning and understanding inheritance if I wasn't going to use it?

In hindsight, it was funny to see the way I thought I had a good grip on inheritance and yet there I was, happily writing lines and lines of duplicate code. In the end (thankfully!), I found a way to make some serious use of my superclass and also learned a bit more about how I should be thinking when I'm trying to use inheritance. I guess what I'm trying to say is that it most certainly pays off to actually try applying the concepts we've learned on our own, even when we think we fully understand something.

On to Exercise 3 this weekend I suppose, so wish me luck!

Week 7: Recursion

Let's start with what recursion is...

Recursion is a method of solving a problem that is made up of smaller problems that are all of the same format as the big problem.

At first glance, this seems both confusing and somewhat useless. How am I supposed to solve a problem that is made up of essentially itself? For me, the key part to understanding recursion was the idea of having a base case and a recursive case. The base case is simple and easily solved and the recursive case is made up of the smaller problems that look like the main problem. So the idea is that all the recursive cases will eventually boil down to the base case (which we can solve) and then we can solve the main problem.

The structure of a (very basic) recursively defined function can look something like this:

       def big_problem(n):
           """ Solve this problem recursively. """
      
           # Base case
           if n == 0:
                  do something
           # Recursive case
           elif n != 0:
                  do big_problem(n-1)


Now if we think about this, for smaller recursive cases (i.e. 'n' is small) we can trace by hand what to do and eventually get down to a solution in terms of the base case which we can solve. But what if 'n' is very large or the body of the recursive case is more complicated than the function above? These are situations where recursion shows its true value. It can take a complicated solution to a problem and turn it into a very simple solution to code, provided of course, you can identify when to use it. And the easiest way to do this is by checking the definition given at the start.

So it's two thumbs up for recursion from me, adieu!

Week 6: Growing tree knowledge

As a follow up to the Tour of Anne Hoy, I (oddly enough) managed to figure out a solution to the tour_of_four_stools right after I published my post by refining my shakier ideas so I was pretty happy. :D The time module gave me a bit of trouble but hopefully what I submitted was good enough to get me a decent grade.

As for this week, we looked at the definition of trees, how we could represent them as nested lists  and we also spent some time on binary trees. It's quite similar to graphs (of graph theory) which I'm familiar with and I've also seen a recursive definition of binary trees in CSC240 so it wasn't too much new terminology. We also looked at  the three different kind of traversals that we can do: pre-order, in-order and post-order. Pre-order traversals are pretty easy for me to think about but for the other two I have to keep reminding myself of the definition when I'm going over the examples.

Reading week is here! :D ...so time to get started on studying for my CS midterms.

Until next post, ¡adiós!

Week 5: Towers of Anne Hoy

As a follow up to last week's blog, I did a little reading on property. I found Tamara's post to be helpful, so many thanks!

In this week's news, the Assignment 1 which is due on Thursday has been my focus. I've ploughed through Steps 1-4 and coded (perhaps not as elegantly as I could have) the pieces needed for the 2D and console versions of the game to work. But, (why is there always a but?) now I'm stuck in a rut for Step 5. I've managed to recursively code the M(n) function but I have no clear ideas for how to code the tour_of_four_stools. Hopefully some sleep and messing around with some of my shakier ideas will get me to where I need to be.

Until next time, enjoy this stack of cheese.

Photo credit to amelstrange of wordpress.