The Big ‘O’: Sorting and Efficiency

If you have made your way to this page, by searching for something else, I am sorry.   The big ‘O’ relates to the efficiency of a program, maybe not what you were looking for.

The efficiency of computer programs has been a long-standing concern with programmers.   The first computers to say the least were not efficient at all.   Taking hours or even days to sort through files of data.   There have been several different types of sorting algorithms presented to us.    In CSC108 we learned about selection sort, insertion sort, and bubble sort.      Programs like selection sort seem to have no applicable applications besides as a teaching tool.   With both the best case and worse case scenarios being O(n²).   The bigger the dataset the more extreme the time becomes in sorting.

Bubble sort is a little bit better.   Although the worst case scenario bubble sort is no better than the selection sort, but in the best case with an already sorted list runtime is O(n).   Insertion sort has similar efficiency as bubble sort, in both the best case and worse case scenarios.  That was CSC108.

Now, CSC148 has taken this even further.    With a more in-depth look at efficiency, we studied more sorting algorithms, such as merge sort, quick sort, and the built-in sort function of python, timsort.   The performance of each of the sorting algorithms in the worst case is better than everything learned in CSC108.  The runtime is O(nlgn) in worse case for timsort and merge sort.    In quick sort the runtime is O(n²) in the worse case.   In the best case scenario merge sort and quick sort are both O(nlgn) and timsort is O(n).     Merge sort and quick sort work similar to each other.   They take a python list and divide the list in half several times.   The difference arises in the selection of the pivot point in quick sort.   In the worse case the pivot point is always the lowest value in the list.   Doing it this way means that the program has to keeps separating the list unevenly.   In the best case scenario the list is roughly divided in half by the values greater than the pivot and values less than the pivot.   These new lists are then sorted the same way recursively calling the quicksort function.

In merge sort, the list is divided in half, and then half again, and so on until, there is one value in each list.   Then these smaller lists are compared to each other, and the value of list is merged with the other in order.   The smaller of the 2 values is merged to the new list first, and then the next comparison is made.

Pyhton’s built in function timsort would be the best sorting algorithm to use, based on the ones that have been presented thus far.    In the worse case it is O(nlgn) and only gets better in the best case.   

The implementation of sorting algorithms can help us study the overall performance of most any program that we write.   Understanding the underlying methods that python uses and how many times we make 'unnecessary calls' can really increase the overall efficiency of a program and less time waiting.

Recursion

Initially I thought the use of recursion would only be useful for certain things, but not necessarily have a big impact on anything else.   But the more I sit through this class and others it has became apparent of how important it really is.  Most recently I was sitting in an actuarial science class, and the occurrence of recursion came up.  When determining a value for a function it was dependent on the value of the function 1 prior to it.    So to find out the value of a function at n +1 you need to know the value at n, which means you need to know the at n-1, and this depends on n-2, and so on until you get to 1.   For recursion to work there would always have to a base value for the beginning of the function.

Another function that was recently brought up in Calculus was the Fibonacci sequence.   This sequence depends on the knowing the 2 values prior to it.   Therefore you would need to start with 2 base cases.   Really any sequence of numbers that is related to a function prior to itself will use recursion to determine the current value.

There are many other things that will make use of recursion.   In our first assignment we needed to use it to determine the minimum value of i for a function.   We also needed to use recursion to move cheeses from stool to stool.

So to conclude, I initially felt like recursion would be useful for a small portion of problems.   However the more I learned about the more useful it becomes, and can be used in many real world problems for solving different programs and functions.

Assignment 1 thoughts

So it has been awhile since my first post.   As I am much older than most if not all the students in my class, I did not grow up with social media being in the forefront of everything.  So please forgive in the delay of posting.  When I was in high school Facebook and twitter were not even ideas. ICQ IMing was the big thing (for anyone who knows what that is they will be able to figure out my age, for those that have never heard of it, you will definitely realize I am much older).   It wasn’t until part way through my first University degree that Facebook even became relevant.  So the idea of sharing my ideas on a public place is not the norm nor that welcoming for me to do.  I have a Facebook account, but don’t post my random thoughts, as I feel this is not appropriate, and use it to only to stay in contact with older friends (which is the premise of what Facebook was designed for).  

Many things have happened during since my first post.   The main thing was the submission of our first assignment.   It was designing a program to run by both user input and computer simulation.    The basis of the program was to model the problems in the Tower of Hanoi. For more background on this here is a wiki article: http://en.wikipedia.org/wiki/Tower_of_Hanoi).  The premise of the game is to move ‘cheeses’, disks, or rings from one platform to another.   You are not allowed to put a larger on top of a smaller object, and have to get all objects to the last platform, using a total of 3 platforms.

The difference in this assignment is we had to incorporate the use 4 stools, and designed a method for moving n-i cheeses using all 4 stools to an intermediate stool then moving the remaining i cheeses to the final stool, and once again moving the n-i cheeses to the final stool.    “i” is chosen as an arbitrary number.   Although each function design was not entirely long in terms of amount of code, the integration of these functions was interesting.   When first reading the assignment it seems overwhelming and a daunting task, but I found that once I started writing the starting code it became clearer on the overall task for the first 4 parts of the assignment.    Once the starter code functions were written, implementing the user input portion of the assignment was fairly simple and actually fun to do, as you got to be a little more creative on the look of the output of the program.

However the last portion in determining the optimal i cheeses to move was much more difficult.   As I sat staring at my screen late at night before the assignment was due with nothing useful working in solving the problem.   I decided to go to sleep.   As I was nervous about doing this and then not having the time to finish it the next day, I went to sleep.    However, this was the best idea.   After reading some useful Q&A on the Piazza discussion board, it just came to me.  This was the biggest relief after testing and making some minor adjustments to the code, and seeing that it worked.

This assignment was a great emotional ride.   At certain points it kind of makes you dislike computer science, but then you complete something on your own and it works, and makes you absolutely love computer science.   This is all for now, and hope to post some more in a shorter time then my previous post.    Look for some thoughts on recursion next week.

Object Oriented Programming

We have been studying Object Oriented Programming and have found it interesting to say the least.   As the structure and presentation of the course material has been much different than taking CSC108, it has taken some time to adjust to a different way of learning.    The readings that have been posted have been lengthy but informative.  I did not fully grasp the concept of Object Oriented Programming (OOP) from CSC108, but found the reading posted about OOP from week1 readings most useful.    There was one analogy that has really stuck with me from this reading.

“It may be helpful to think of a class as a factory for making objects. The class itself isn’t an instance of a point, but it contains the machinery to make point instances. Every time we call the constructor, we’re asking the factory to make us a new object. As the object comes off the production line, its initialization method is executed to get the object properly set up with its factory default settings.”

This gave me a good understanding of what making a Class is all about and strangely enough why we would want/need to make a new Class.    Being able to define your own classes allows you to build your own uniqueness to programs.   Being able to change an equality method to make it unique to the class or changing any other built-in method to make it perform how the designer of the class wants it to is quite interesting.