Sorting and Algorithm Efficiency

The past few weeks, we have focused mainly on the different major sorting algorithms and their efficiencies compared against each other. The sorting algorithms that we have been learning are selection sort, insertion sort, bubble sort, merge sort, quick sort and Python’s very own Timsort.

Big-Oh is a way to describe the efficiency of an algorithm in the worst-case scenario. It is determined by rate of the growth of the number of steps which an algorithm takes as the input increases. Big-Oh can be categorized anywhere from constant (O(1)) to exponential (O(n^n)). The symbol for Big-Oh can be confusing at first because it does not allow the usage of a constant multiple, as it is already implied. If the algorithm grows at a rate of 3n, then it is included in the case for O(n). O(n) means that the algorithm grows at a rate of any constant multiplied by n. The goal of measuring Big-Oh is to see how well your algorithm performs under the worst-case scenario then to determine where it is possible to improve your algorithm.

The worst-case scenario efficiency of these sorting algorithms are O(n^2), for selection, insertion, bubble and quick sort and O(nlogn),  for merge and Timsort. Although quick sort has a quadratic Big-Oh for worst-case scenario, in real world applications it is incredibly fast. http://www.sorting-algorithms.com/ has a great visualization of the different sorting algorithms (excluding Timsort). Here you can see quick and merge sort are much faster than insertion, selection and bubble sort. The only list where quick sort appears to have trouble is lists that have few unique items. Robert Sedgewick and Jon Bentley noticed that quick sort has these sub-optimal performances and decided to make some tweaks to the algorithm and managed to optimize performance in quick sort. The adjustments are posted in this presentation: http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf.

What I observed with the visualizations, I also observed in lab where we had to compare how all of these sorting algorithms with inputs of 400, 800, 1200, 1600, 2000, and 2400.

As you can see in these graphs, the speed difference between selection, insertion and bubble sorts compared to merge, quick and Timsort is quite large on every type of tested list. Learning the differences in sorting algorithms were a great lesson is why computer scientists need to always analyze their algorithms and work to create algorithms that are as efficient as possible.

Recursion and Linked Lists

The underlying programming technique that we have been focusing on throughout CSC148 is recursion. It has its hands on pretty much every aspect of the course, from our first assignment to our labs to our second assignment and everything in between. The professor is teaching us how to use recursion to solve simple problems like determining fibonacci numbers and more difficult problems like creating recursive data structures, such as trees and linked lists.

I never understood how powerful recursion is until I began to use it to create data structures My personal favourite use of recursive data structures is the linked list. A linked list allows the user to build an abstract data structure with much more efficiency than a regular list. In lab I was able to use a linked list to recreate a queue similar to one I made earlier in the semester using a a regular list with much more quicker results to enqueue and dequeue a very large amount of items. The linked list allowed me to delete the item at the front of queue without adjusting every other item in the linked list whereas a regular list must move every item. Every item in a linked list has its own memory space that contains a reference to the following item, so to add an item to the front or to append an item at the back, the user only has to create the memory block and change the reference to head of the linked list or add a reference to the final item in the linked list.

Recursion is a very powerful technique that I now know I will be using for the rest of my programming career. I am excited to use this new knowledge and build on it throughout the final half of CSC148.

Inheritance and Testing

Lab this week was spent learning more about class inheritance and unit testing. These were both parts of programming that I did not have a lot of experience with before this week. Creating classes have been getting much easier with the practice I have been doing between class exercises, labs and home programming. Practicing has helped speed up the lab, and focus on inheritance and unit testing. It was interesting using parent classes to handle repeat code as a more advanced version of building new functions to minimize repeat code. Inheritance helped me reduce the code written for the motorized and human-powered classes and further subclasses during lab.

Once the code was cleaner using inheritance, my partner and I moved on to unit testing. We both had experience with the assertEqual function but little else with unit testing. My favourite new function to learn was the assertRaises function because this allowed me to apply my newly gained knowledge of exceptions from last week. Personally, I love when topics connect so well in my courses, so being able to combine exceptions and testing together was very exciting. 

Now I will be heading into the first assignment applying these new skills towards creating cleaner, more powerful code. I look forward to sharing my struggles and breakthroughs in my future posts. 

Object-Oriented Programming

I'm sure you have heard this a few times, but welcome to my SLOG! So this week we are going through my adventures of OOP (Object-Oriented Programming). I got a brief introduction to OOP back in CSC108 and now that I have started CSC148, the professor has been ensuring the students are more comfortable with OOP from the beginning. As the course has been moving through the year, I have learned a little bit more about OOP and Python as a whole. This week the professor focussed on exceptions in class and the TA was teaching us how to find and use new modules, both of which are a type of OOP but have very different aspects.

During class this week, the professor gave us our first introduction into raising and creating our own exceptions. As I've never created an exception subclass, this was a completely new concept to me. Creating my own exceptions has allowed me to utilize Python's class inheritance. While I enjoyed learning about creating exceptions, it wasn't the easiest concept to grasp from the beginning. To fully learn to independently execute this function, I not only had to review the lecture notes, but I had to rely on external research as well. I watched two very helpful YouTube instructional videos that gave me guidance on how to properly execute the exceptions. The most helpful video that I found was a tutorial from Lynda.com. This video was especially helpful because it uses live examples to demonstrate the functions, you can view it below.

Raising Exceptions
Lynda.com Tutorial

By the end of exercise 2, I believe I know what each function now does and when to raise each one. While learning more about inheritance and subclasses, I was also learning about creating my own Abstract Data Types (ADTs) in our lab. We focused on creating stacks and queues and how each has its own strengths and weaknesses. At first, it seemed like stacks were far superior because the speed of using the stack class stayed constant as the inputs increased in size, while the speed of using the queue class increased linearly. During the lab the TA gave my partner and I recommended that we spend some of our own time researching new data types to use with the queues. While we were researching, we stumbled upon the collections module and the deque data type. When we implemented the deque data type into our queue, it increased the efficiency of the queue class to become constant like the stack.

I look forward to continuing my education of computer science and learning and becoming more self-sufficient as I work on my programming skills. While I expand my knowledge of computer science and improve my programming abilities, I will strive to enhance my blogging skills so that each post is interesting and helpful to my readers.