Week 11: Sorting and Efficiency!

Over the past couple of weeks, the lectures have been focusing on the topic of sorting and efficiency. Sorting is one of the main processes in computer science, and it involves arranging elements from a list in some desired order. Computer scientists have come up with numerous sorting algorithms over the past couple of decades and some of them are naturally more efficient than others. Needless to say, it is important for computer scientists to find the most efficient sorting algorithms in order to optimize performance, and hence we analyze some of the most common sorting algorithms below.

Among the most famous algorithms are bubble, selection, insertion, merge and quick sorts. Bubble sort involves comparing adjacent items and exchanging those out of order; in each subsequent pass through the list, the algorithm places the next largest value in its proper place. It sort is by far the least efficient algorithm, having a performance of O(n^2) in every single case and having to exchange values in every single comparison in its worst case. Not very far ahead is selection sort; in each pass of this sorting algorithm, the smallest value in the list is placed in its proper location. It has an average performance of O(n^2), but unlike bubble sort only one exchange has to be made in each pass through the list. Insertion sort is slightly more efficient than selection. This algorithm always keeps a sorted sublist in the lower indices of the list; in each pass through the list, the next item is placed back into the right position in this sublist, making the sorted sublist one element larger until it contains the entire list. Insertion sort has an average and worst case performance of O(n^2) like bubble and selection; however, it is much more efficient when it comes to its best case, in which its running time becomes O(n).

Compared to bubble, selection and insertion sorts, merge and quick sorts are considerably more efficient. Merge sort is a recursive sorting algorithm that works by repeatedly splitting the list in half until its two halves are either empty or have a single item; then, it works by merging the two halves in the correct order, continually until the entire list is merged in the correct way. Quick sort involves recursively partitioning the given list using a  pivot value into two different parts: the left (everything that has a lesser value than the pivot) and the right (everything that has a greater value than the pivot), and recursively calling quick sort on each of these parts until they have length less than two, in which case they are already sorted. Quick and merge sorts have an average efficiency of O(n log n), so that their performance is roughly equivalent; however, in its worst case, quick sort's performance drops to O(n^2) as the pivot can be selected to be the greatest element of the list in each case, splitting the list into two very uneven halves.

Python's built-in sorting algorithm, however, is by far the most efficient, as it is a hybrid of different algorithms including merge and insertion sorts; it also takes into account the ordering of the given list, making the algorithm more efficient based on the specific case.

Week 10

Assignment 2 part 2 was due this week, and, surprisingly, I found it very straightforward! Although painfully long, functions is_regex, all_regex_permutations, and build_regex_tree were particularly uncomplicated (even though they might look very complex at a first glance).

On the other hand, regex_match function was slightly harder. The trickiest part of this function was in having to check whether a given StarTree matched some string. This is because this involved splitting the string into all possible concatenations of any length, and I found this especially tricky; at the end, I ended up doing this recursively by splitting the given string into two parts in all possible ways and then recursively splitting these two parts in all possible ways until I had all possible concatenations of the string. This made my function particularly confusing and not very efficient, in my opinion, but I could not find a better way to do it; the code was actually so inefficient that when checking whether a StarTree matches a very long string, Python took a painfully large amount of time to perform the task. In some cases, it even crashed as there was not sufficient stack space.

This week's lab was slightly harder than last week's. The first task, which required us to write an inorder traversal for a binary tree, was much simpler than the second task. The second task was to write code for a function named longest  that takes the root of a binary tree as argument and that returns the first node in a linked list that contains every value in a longest path from the root of the binary tree to one of its leaves. This was particularly hard since we were not allowed to utilize an intermediate Python list or similar container class to keep our information temporarily. In the end, we were actually successful in writing this challenging function, but it appears that we did it in a way other than expected. Our code utilized a helper function that kept track of the length of the longest path so that it would keep adding new nodes to the linked list until its length was the same of that of the longest path.

During this week's lectures, we went over more "big-oh" material as well as were introduced to two new sorting algorithms: merge and quick sorts, of which I will talk about in detail next week!

Week 9

Over the course of this week, we started covering material about the "big-oh" in lectures.  The so-called "big-oh" refers to the running time of different algorithms. The most common analysis of "big-oh" performance is in different sorting algorithms, as I will cover in depth on week 11. The different efficiencies of Python algorithms depend on the function's running time, which include constant, logarithmic, linear, and quadratic, among others.

Some of the different types of sorting algorithms that we went over in lecture this week included insertion and selection sorts, which we had already learned about in CSC108 so it was mostly review material for most of the students.

This week's lab was particularly straight-forward as it involved writing the method count_less for the class of binary search trees in several different ways. The first way was by writing a nested helper function within method count_less, and this was very easy as we were allowed to make use of recursion. Other ways included having to not use None as well as implementing a helper method in the class _BSTNode. The hardest way we had to write this method was the last; we were expected to write the method non-recursively by instead making use of iterations. Surprisingly, this task was very uncomplicated and easy to understand as my partner and I utilized a for loop.

Week 8

During this week, we received our midterm marks back, and to be honest I was quite pleased with my performance!

In lecture, we covered more LinkedList examples by implementing new methods to the class; this task was particularly straight-forward and involved a lot of recursion. We then moved on to a new topic: binary search trees. Binary search trees are a special kind of tree expressions which have some specific constraints:
-each node in a binary tree can only have a maximum of two children
-data in the left subtree is less than that in the root, which in turn is less than that in the right subtree

This makes searching for a particular node especially efficient since it cuts down the tree by two each time we encounter a new node.

The methods implemented in the BST class further used recursive strategies, as in the method insert and __str__.

In this week's lab, we dealt with more LinkedList examples, implementing some of the methods of the Python class list into LinkedList. Some methods included __setitem__, __len__, and __delitem__. In writing the method __len__, we decided to add a simple attribute in the __init__ method of LinkedList so it would keep track of the length of the list, making necessary changes when the list was changed; this allowed __len__ to be very short and efficient.

This was also the week during which the first part of assignment one was due. Part I was very simple compared to the first assignment; it dealt with a class hierarchy of regular expression trees. The way I created my hierarchy was based on the number of children in each type of tree as well as the specific root node for each type of tree. This made the implementation of methods particularly straightforward.
Part II, on the other hand, seems to be quite challenging. I've begun working on the very first part of Part II, but I still haven't quite wrapped my head around it. Hopefully things will get better next week!