Sorting Out the Big-O

Back in high school, list sorting was like:

>>> l = [6, 8, 3, 5, 1, 2, 4, 7]

>>> l.sort()

>>> l

[1, 2, 3, 4, 5, 6, 7, 8]

Those were good times.

Now I know that there are different ways to sort a list: bubble sort, insertion sort, selection sort, merge sort, quick sort, etc. Learning these types of sorts (whose code and descriptions can be found here) is useful for understanding the difference in efficiency one implementation of a working code can make over another.

The efficiency of a program is determined by how many steps it takes to solve a problem depending on the size of the problem. In the case of list sorting, the runtime would be determined by the length of the list. We count steps rather than speed to avoid including the factor of differences in CPU speed. Computer scientists like to look at the worst case runtime not because they're pessimistic but because knowing the most number of steps a program will take allows for an upper bound to be put on it.

The runtime of a program is denoted as some function of the problem size. This is useful for predicting how much longer a program will take to run as the problem size increases. For example, the function for the worst case runtime of bubble sort is n². This means that if the length of the list were to double, the runtime would be four times longer. Contrasting this with merge sort's nlogn runtime, it is evident bubble sort is not as efficient.

The worst case runtime of a program is denoted as O(function). For example, bubble sort has O(n²) and merge sort has O(nlogn). Bubble sort is jealous.

This is called Big-O notation. Because it's kind of a big deal.
...I'll see myself out now.

A Recursive Forest

When we first started learning about trees in CSC148, I thought they were just another tool to help get across the concept of  recursion. It didn't occur to me how useful this data structure was on its own until we encountered binary search trees.

Binary search trees are trees with the special characteristics of allowing every node only two children with the child on the left strictly smaller than its parent and the child on the right strictly greater than its parent. Having this specification allows us to search for a value in the tree very efficiently. When checking if a number is in a binary search tree we first check to see if it is the root. If not, we compare the value of the number to whether or not it is less than the value of the root. If that is the case, we know that if the number is in the tree, it must be located in the left subtree; if not, we know that we should do the remaining checks in the right subtree. This method always eliminates half of the tree or subtree it checks giving it a runtime of O(lg(n)).

Linear search, please exit stage left.

Codepanda vs. Recursion

Recursion and I met several years back. We did not get a very good first impression of each other and ultimately decided it would be best to go our separate ways. Time went by and our relationship dissolved into nothing. That is until we suddenly bumped into each other in CSC148 this semester. Talk about awkward....

The problem I had with recursion was that it could not be traced like for loops or while loops. When I first encountered it, recursion was explained in an extremely confusing way. Apparently a way that humans should not learn it. Throughout the past month I attempted to relearn recursion and I think I have gotten the basic idea of it.

Recursion is basically observed as a function calling itself. You can see how this ties in with the idea of looping. Programs that are recursively implemented can often be written with regular loops. However, the power of recursion lies in the efficiency it provides for the program. Code written to solve a problem recursively will run faster than code that solves the same problem with a loop.

There are two components to the basic recursive function: the confusing, self-calling function part and the base case.

The base case is what you want the function to do when the simplest, most basic argument is passed in. For example, if you want to determine the sum of the values in a nested list, the base case would be the function's behavior when a flat list is given. If you wanted the function to calculate a number's factorial, the base case would be evaluating 1! (exclamation mark = factorial symbol, still using my indoor slogging voice).

The recursive part is used when the function is called with a more complicated argument. The function essentially breaks down the problem into smaller parts until it reaches the simplest problem which is the base case that it knows how to evaluate. Then it retraces its steps and fills in what it knows in order to give an answer to the original argument inputted.

The basic structure of recursive code is:

def function(arg):
        if base case:
                evaluate to this
        else:
                evaluate something with call to function(with_some_arg)

Whether the base case/recursive part are under the if or under the else clause is arbitrary.

The base case is very important since it tells the function when to stop recursing. Without the base case, the function will endlessly run the recursive call until python runs out of memory and leaves.

Here is a great example of a recursive function and how it works -> great example

except: BadTitleError

Today's topic is all about exceptions.

Exceptions are errors that happen when something goes wrong in the execution of a python program. Having said that, I will not be talking about syntax errors in this post (because syntax errors and I are not on speaking terms).

Say, for example, you wanted to write a program that tells users what a certain number multiplied by 3 evaluates to. Here is what you may come up with:

def times_three(num):

        return num * 3

(Yes, the colors do not match the ones in Wing IDE. I got used to IDLE. Leave me alone.)

The function above works perfectly fine. However, to allow users to be able to use it to type in their favorite number to be multiplied by 3, you may decide to add a few lines to the program that allows for user input.

def times_three(num):

        return num * 3

num = input('Please enter your favorite number: ')

float(num)

print(times_three(num))

Doing this makes you a nice person but it also opens up the risk for your program to fail.

The program wants only to submit floats as an argument to times_three so if the user were to enter anything that is not a number then the program would crash.

The wise Python has foresaw these types of errors caused by improper object types, outrageous math operations, and trolls which can all destroy the self-esteem of a perfectly legitimate program. In order to prevent the program from just giving up and going home, we can raise exceptions.

In this particular example, a built-in ValueError is hit when running the program with a non-number input. We can notify the user when this error is detected by using the python try/except notation. That will simply try to run the section of code that may cause a problem (in this case converting the input into a float) and if it does not work properly we will raise the ValueError exception.

def times_three(num):

        return num * 3

num = input('Please enter your favorite number: ')

try:

        num = float(num)

        print(times_three(num))

except ValueError:

        print('Not a number. Go away :(')

Everything in the try block is attempted first. If it works, the program runs as is expected. If not, the ValueError is raised and the details of the error are shown to the user.

Doing this allows the program to terminate cleanly.

In addition to using built-in exceptions such as ValueError or ZeroDivisionError, python also allows you to write your own exceptions by defining them as a class and having them inherit from the all mighty Exception class. (I originally wanted this to be an example of that but then python flashed its built-inValueError card at me halfway through...)

In a more exotic program, there may be more than one risk with a certain block of code. In these scenarios, it is possible to have more than one except clause to catch different types of exceptions. The important thing to remember with those is that Python will go through them in the order that they are listed. This means that the except clauses should be put in the order of least specific to most specific in terms of the scope of the errors they catch.

I found Professor Heap's example to be very helpful when thinking of this. One thing that will always be certain is that if you want to catch all exceptions and use the all-inclusive Exception class then it should always be the last except clause.

On Object Oriented Programming

The majestic Python exists within a object oriented habitat.

Programming in this language is all about manipulating objects: determining their properties, figuring out how they should behave, etc. The way to establish the characteristics of a certain object is to create for them a class which serves as the blueprint of their production. This is a powerful way to code since it allows us to be able to create Python objects which can model the objects of the real world. For example, in Exercise 1, we created a Dog object which was equipped with a name and the ability to play with a toy much like a dog in real life. 

It gets even more interesting when different objects interact with each other. In the previous example, the toy the dog plays with is a separate object that follows it's own class' blueprint. In the same way that a real toy would behave, the dog object interacts with it to bring out its behaviour.

Another ability a programmer has in OOP is to create a subclass based on another class. For example, there may be a class Food with food objects and from that a subclass, Fruit, inherits the attributes of Food with its own unique specifications. This is not unlike how we organize and classify objects in life.

Object oriented programming brings out a connection between the real world and the virtual one.