Week 11: Sorting and Efficiency

The past two weeks in class, we have looked at different types of sorting algorithms along with their runtime, which was also seen in big-Oh notation. In the lab this week, we also ran different types of sorts and noted their run time in comparison with others, but also ran these different sorts with three different types of lists of various sizes: random, sorted, and sorted and reversed. Through this lab, I saw that the python built-in sort was the quickest because, as our T.A. explained, all built-in python functions are written to be the most efficient; therefore, if there is a python built-in function, we should use it instead of writing our own code for it.

In CSC108, we were introduced to some of the different types of sorting algortihms, which included insertion sort and bubble sort. The algorithms we ran in the lab included these ones, as well as merge sort, quick sort, and selection sort.

Quick sort:
Quick sort works by choosing a pivot and then splitting the rest of the list into two, those greater than the pivot and those smaller than the pivot. Then, quick sort is performed again on the two separate lists. We looked at run times for choosing a pivot at the beginning of the list or choosing a pivot at random. When chosen at random, the run time was smaller than when the pivot was the first item because if the list was already sorted, in either ascending or descending order, the code would have to make every item a pivot before the code is complete.

Merge sort:
Merge sort works by splitting the list in half continually, then sorting and merging each of these halves until the list becomes one sorted list. The run time of a sorted, random, or sorted/reversed list is the same every time for merge sort because it will always perform the same steps, no matter what order the numbers are in. The big-Oh notation for merge sort is O(nlogn).

Binary Search Tree & Assignment 2 Part 2

So far, we have learned to work with trees in our labs, lectures, and assignments. One of the trees we worked with, which I found interesting, was a binary search tree. A BST has an arity/branching factor of only two. Every node contains a value for which every node on its left subtree, the values are smaller than the parent value, and every node on its right subtree, the values are greater than the parent value. This comes in handy, as seen in the lab, when trying to find the number of nodes that are less than a certain value. We then combined our knowledge of binary trees with linked lists in this weeks lab when we created linked lists of an inorder traversal of a binary tree. This was difficult at first, but was solved by using a recursive call on a function within a function. Although difficult to grasp at first, through practice with different methods that included recursions, the task got easier, though I still need to work on it more.

I also had more practice with recursion in the assignment due this week where we tested for valid regular expressions and created the regular expression trees for each of the valid string expressions. The most difficult part of this assignment to me was figuring out how to determine a valid regular expression from a string input as there were many regexes within the main regex. It was difficult trying to find out which of the '.' or '|' was part of the first regex. The next difficult task was trying to find with regex was equivalent to which string. This was solved by using different if statements and lots of recursion.

In conclusion, this week has been fairly difficult and busy, but helped me with recursion.

Labs, Assignments, Exercises

This week has been a busy week in CSC148. In our labs, because many of us could not figure out the LinkedList problem, we had another chance to tackle it. This time, we were given hints as to how to implement LinkedList into class Queue. In trying to solve the Queue problem, we figured out ways to write the __len__, __delitem__, __setitem__, and insert methods for class LinkedList. A couple things I learned from this lab was that, in Queue, the front and back of the Queue were initialized as two separate empty items themselves, rather than try to figure out from a non-empty Queue which item was in front and which item was in the back. This turned out rather useful as we were trying to index the Queue earlier on but had difficulty in enqueueing and dequeueing items this way. Creating the two attributes (self._back, self._front) was much easier in completing the tasks.

Another thing that we had been working on this week was the assignment for regular expressions (regex). We were to write separate classes for each of the different regular expressions. I decided to write a basic regex class, called Regex, from which the other classes would inherit properties. I then made four other subclasses of Regex, called LineRegex, DotRegex, StarRegex and LeafRegex. Each will have an __init__ method, a __repr__ method, and an __eq__ method. Though a LineRegex and a DotRegex are similar in properties, I decided to write them as two different classes because they have different ways of being equivalent to another Regex.