Week 12: Run time complexity

CSC148 has come to a glorious conclusion! But before the curtain closes, we still have one final very important topic to discuss. All roads lead to this topic. So without further ado.

“Run time complexity”, what is it? and why does it matter?

In class we were introduced to different types of functions. What separates the best function from the worst is the time it takes to accomplish some task. Whether the task is sorting elements in an array, finding the factorial of a prime number or otherwise, a well written function should provide an output in the fastest time possible. For this reason, the run time of a function is a hot topic around these parts.

Once the run time complexity of a function is established, we place it into one of several different categories. As you study the running time and data size tradeoffs in the graph below, you’ll notice that some of the least efficient functions would fall into the n^2 category, while some of the best would fall into the constant time category.

How to figure out a functions run time

So how do we go about figuring out which category a function belongs to? This is done by counting each time a function’s line is executed, under the worst case condition for some number of inputs n.

Let’s get a better sense of this counting method with a simple example.

Counting example - search_lst function

Our function:

def search_lst(lst, obj):

“”” Return index of obj if it exists in lst, otherwise return -1 “””

1. i = 0
2. while i < len(lst):
3.   if lst[i] == obj:
4.       return i
5.   i = i + 1
6. return -1

Let’s assume that the object obj we’re trying to find in an arbitrarily long list lst does not exist in lst.  In other words, this is our worst case. The while loop will iterate over every index of lst but it won’t find the desired obj.

Now that we’ve established the worst case scenario, we can begin thinking about how to count each line of code in search_lst. The length of lst is some arbitrary length that we’ll refer to as n. The table below enumerates the amount of times each line of code is executed.

Code line	Code	Times executed
1	i = 0	1
2	while i < len(lst):	n + 1
3	if lst[i] == obj:	n
5	i = i + 1	n
6	return -1	1

While most of the times executed counts are self explanatory, the one that confuses most people (including me) is the count for line 2. Line 2 of the while loop is executed n + 1 times because n’s the number of indices of lst and 1 additional time, that extra time being the loop guard, which makes sure to escape the loop once the inequality is no longer true (i greater than len(lst)).

Looking at the times executed column we can formulate a run time complexity for search_lst by using some basic arithmetic. We see that n appears 3 times and the integer 1 appears 3 times, so this gives us 3n + 3, which is the linear run time of search_lst, hallelujah! It’s that simple.

To conclude then, we’ve discovered that search_lst belongs in the linear category of time complexity. The time it takes to execute search_lst in the worst case is directly proportional to the size of the input (in our case the length of lst). Could the run time be improved for this function? Could it become constant time? perhaps, but this is where we’ll leave this for now. It’s been a pleasure!

Week 11: Revisiting an earlier post

With 2 weeks remaining of CSC148, we’re given time to revisit and reflect on an earlier post of our choosing. I’ve decided to return to my very first post: “The pen is mightier than the board” (Week 3), where (as a would be programmer) I briefly discuss the advantages of writing frequently and effectively.

I’ve also read classmates posts on this topic, so that I may get their impressions on why it’s important to write effectively in our line of work.

Challenging but pays off in the end

Writing is not everyone’s “cup of tea”, that much is clear. Writing slogs for CSC148 that were both informative and engaging was a challenge. But looking beyond our slogs and into the future, this writing could very likely take the form of supportive documentation, error logs, blogs and yes even long email chains. I was convinced in my first week, and I still remain convinced, that consistently writing on any relevant topic of programming, sharpens our minds and better prepares us for what I expect to be collaborative future work environments.

It’s all about communication 

A fellow classmate js Lim provided a quote in their post, “If you can’t explain it to a six year old, you don’t understand it yourself.” As blunt as this quote may be, it gets to the heart of the matter. To feel comfortable with programming concepts and confident in our abilities to use these concepts, we should be able to communicate how a snippet of logic works to clients and teammates that possess varying degrees of experience. Now in days, a big portion of this “explaining” comes in the form of written communication. Flexing our creative writing muscles now assures us that when push comes to shove, we are able to defend our ideas and convince others that our rationale is correct.

Week 7: Recursion

Recursion is a programming methodology that at first may be difficult to wrap your head around, as it was for me, but once understood, the possibilities are endless! (well sort of)...

Recursion, but why?

What does a recursive function do? and why is it useful?

At its core, a recursive function is a function that calls itself, and continues to do so until a condition is met.  It breaks down a difficult task, into smaller, more manageable subtasks, until the final task is trivial and the problem is solved. The lure of a recursive function is in its simplicity and power. A couple of lines of code can do a lot of heavy lifting.

To truly appreciate the awesome power of recursion, lets consider a list that is composed of arbitrarily nested child lists, much like the following:

[ ‘a’, ‘b’, [ ‘c’, [ ‘d’ ], [ ‘e’, [ ‘f’, ‘g’ ] ] ] ]

If you were tasked to write a “list counter” program that counts every instance of a list within the list above, how would you go about doing it?

The inclination would be to write the program as a series of nested loops. You’d want to traverse each child node in the list, check if it’s an instance of a list type, go onto the next child, check if itself has children, all the while keeping track of the length of a child list, adjusting the iteration and counter accordingly. Implementing an algorithm of this type is, as I’ve discovered, quite difficult.

The makings of a recursive function

There isn’t anything inherently wrong with the “list counter” algorithm as described above. Theoretically, if we could code it, it would do the job. To make our life easier though, we could attempt to “recursify” this algorithm. Before we can do that, we need to know what makes a recursive function so darn recursive and why it would work in this particular case.

A recursive function must satisfy the following principles:

1. Has a basecase

2. Moves towards the basecase

3. Calls itself recursively

The basecase of a recursive function is its “escape route” and it should always have one in mind. A recursive function should end at some point and it ends when it reaches its “escape route”, its basecase.

It may be a long and tiring journey to the basecase but it should always be moving towards it.

Finally, the function should, at every stage of the journey towards the basecase, call itself.

So why would recursion work so well in our case? Because we can simplify the problem down to a few important tasks that are repeated over and over until a certain condition is met.

The tasks are:

1. Checking whether an object is of type list

2. Incrementing the counter if an object is a list

Those 2 tasks are the basis of our recursive function.

Putting recursion to use for “list counter”

Lets put these recursive principles into action and code ourselves a “list counter”, shall we?

def list_counter(lst, count=0): # We give the count a default value of 0

  

   # Loop through each item in lst

   for item in lst:

       

       #Basecase: Is item of type list ?

       if isinstance(item, list):

           

           # Recursive self call: If item is a list,

           # then call list_counter  with nested list

           # and incremented count as arguments           

     count = list_counter(item, count + 1)

   

   # return value of count for each stage

   # of recursion when basecase is reached

   return count

We can get a better sense of the recursive nature of list_counter() by referring back to the 3 recursive principles we were introduced to.

1. Has a basecase

Indeed list_counter() does! The basecase being, a lack of objects that are of type list. The only way this recursive function will end is by no longer encountering nested list objects at each level of recursion.   

2. Moves towards the basecase

Everytime list_counter() encounters a nested list and then dives into that list by making a recursive call to itself, it is getting closer and closer to a point where there will no longer be a nested list, that point being its basecase.

3. Calls itself recursively

When list_counter() encounters a nested list, it calls itself, and passes itself the newly discovered nested list and an incremented instance of the variable count.

Week 6: A world of objects

Our discussion of Object Orient Programming in week 6 has a close connection to the 4th week discussion on Abstract Data Types. In a way, this post continues from where we left off in week 4.

As previously discussed, an Abstract Data Type describes a solution to some programmatic problem. When an ADT is implemented it becomes a class and instances of this class are called objects. With that, we have our foray into Object Orient Programming!

Object state and behaviour

Objects in computer science often correspond to things found in the real world. One such object could be a car, telephone or even a dog! It could literally be any object that a program needs to handle. What I find most appealing about Objects in the programming world, is that they are self-contained modules that bind methods to the data they contain. Put simply, objects are neatly organized packages of methods and data that can be easily used over and over again.

Most (if not all) objects contain some data during their lifetime. This data describes their state at any given point. An objects data does change, It’s added, removed and updated by functions that are specifically designed for this object. We can get a sense of what an object is meant to do by reviewing these functions and so we get an impression of it’s behaviour.

Object hierarchies and inheritance

Another interesting thing about objects is that they exist within a hierarchy. The top most object in a hierarchy can pass down some or all of it’s properties (data and functions) to lower objects through inheritance. If a change is required at the bottom of the hierarchy, it is possible to make the change without worrying about the consequences this may have on other objects that are further up the chain.

Week 5: Tracing a recursive function

Like with many other things, it takes time and practice to master recursion. Thankfully we have a technique at our disposal which makes learning recursion easier. This technique is referred to as “recursive tracing”.

Tracing a call to a recursive function is a great way to understand how the recursive function behaves, and inevitably when errors crop up, it’s also a good way to troubleshoot and fix bugs.

Winding and unwinding recursion

When tracing most recursive functions, there are 2 phases that occur one after the other.

First we have the winding phase, which occurs at every level of recursion. It occurs every time subsequent calls to a recursive function (usually the same function) are made. The winding phase will continue until it reaches a dead end, a point which is referred to as the “base case”. The base case is a condition in which further recursive calls are not necessary.

The unwinding phase occurs when the base case condition has been satisfied. It is at this point the recursive process travels back up the recursive levels and returns some final value.

Winding and unwinding is not something native to only recursive functions. We’ve seen this occur with many ordinary functions. Suppose that a function a() makes a call to function b(), which inturn makes a call to function c(). Once function c() has done it’s job, what happens next? It goes back to b() and then a(). So we can think of going from a() → b() → c() as the winding and back from c() → b() → a() as the unwinding.

How to trace a recursive function

Let’s say that we wanted to implement a recursive function called check_for_occurance that checks for the occurrence of some object within a list and returns a boolean value. Object and list are arguments of our function.

Here’s the code for our function:

def check_for_occurance(obj, lst):

   '''(Obj, list) -> Bool

   

   Return True if obj exists in lst (the 1st occurrence of obj), otherwise return False.

   

   >>> check_for_occurance(1, [0])

   False

   >>> check_for_occurance(1, [0, [1]])

   True

   '''

   

   index = 0

   

   # Base case: Is obj in lst?

   found_obj = obj in lst

   

   while not found_obj and index < len(lst):

       

       # General case: Iterate through lst and recurse on item that is itself a list

       if isinstance(lst[index], list):

           found_obj = check_for_occurance(obj, lst[index])

       index += 1

       

   return found_obj

Note: In our implementation we rely on the python ‘in’ operator to do a check for an item in a list. However, it does so only on the first level of a parent list. It ignores nested child lists.

To understand how check_for_instance works, we begin by tracing a simple example and then work our way up to a more complex example.

Simple tracing example

check_for_occurance(1, [0]) → False

In the simple example we see that the list has only one level and therefore does not require any recursive calls. Also, we can see that the integer 1 is not in the list so the function returns False.

Slightly more complicated tracing example

check_for_occurance(1, [0, [1]]) → check_for_occurance(1, [1]) → True

In the slightly more complicated example, the list has two levels. The first level does not contain a 1, but it does contain another child list (the second level) so we need to make a recursive call on the child list. Lo and behold the child list does contain a 1 so we expect to have True returned.

So to conclude then, by tracing out the recursive calls to check_for_occurance we’re able to see what is happening at each of level of it’s recursion and what the return value should be.

Week 4: Abstracting away complexities

When we think of the term “abstract”, perhaps the first thought that comes to mind is abstract art. Abstract art holds little or no resemblance to real world objects. The use of lines, shapes and colours in abstract art is typically no where near accurate. This is why someone looking at abstract art may stare at it for hours without understanding what the piece is meant to represent.

We see this word “abstract” in computer science, but unlike it’s artistic variant, abstraction in computer science aims to simplify and consolidate our understanding of complicated programmatic operations without needing to write a single line of code.

Abstraction in action

To put abstraction to use, we’ll begin with a problem, one that was discussed in lecture and one whose solution was first proposed back in 1946 by Alan Turing.

Problem: Given some items (objects/values etc.), we’d like to build a collection of these in ascending order, and be able to add to the collection, and return the latest item when necessary.

Before we jump the gun and think about the code that could solve the problem, we first need to describe the solution so that we’re able to define a model.

Solution: The Stack model. A Stack contains various types of items. New items are pushed (added) onto the top of the Stack, the latest (or top most) items are popped (retrieved) from the top of the Stack. It’s not possible to pop an item from an empty Stack.

Our solution is fairly basic but it has two important properties which are common to all Abstract Models/Abstract Data Types:

• describes a solution which could be implemented in any programming language
• describes the data it contains and the actions that can be performed on the data

The Stack Abstract Data Type exists independent of any implementation. Abstract Data Types serve as blueprints or recipes so that they may be easily understood and implemented in any given programming language. However, it’s not guaranteed that all implementations of the ADT will work the same. Some implementations may perform more efficiently than others.

Our Stack solution makes references to nouns, such as item and verbs such as pushed and popped. When describing an ADT, nouns become the data and verbs become the actions (or methods) performed on the data. Select nouns and verbs define the underlying structure of an ADT.

So where do we go from here? We’ve defined our Stack ADT, the next step would be to implement it in our favourite language. Once implemented, the ADT takes on the role of a class, which is a topic for another post.