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.

Week 7: Recursion Cont'd

Since I have already made a blog post about recursion, I will add onto it the new material we have covered in class. As mentioned briefly in the previous post, recursion is very useful in ways such as going through nested lists or loops. We were able to see this through our labs and lectures when we learned about classes such as LinkedList and Tree. In a Tree class, nested Trees are known as subtrees, and each node is a child. In order to create methods to count the total number of children in the Tree or calculate the height, it was useful to implement a recursive algorithm. For example, the code provided by the course uses recursion in the method count:

return 1 + sum([count(n) for n in t.children])

For me, recursion is very difficult to trace and I must write out each step of the function. This became a bit of a problem this week when during the term test the first question pertained to this exact topic. However, because of the amount of practice we had in labs, I was able to (hopefully correctly) answer the first question.

Speaking of the labs, I found this week's lab quite difficult when we were to add methods to the class of LinkedList. The first method that we worked on was determining the length of a LinkedList. The problem arose when we could not figure out a way to index a LinkedList, which would be useful in figuring out the length. We tried many different techniques; we tried to write while loops (while the second item in the list was not blank: LinkedList()), as well as trying to append each item to a regular list and determining the length of that list. By the end, we still could not figure out how to write this method, but in attempting different ways at tackling this problem, my understanding of recursion grew.

Week 6: List Comprehension

This week in class, we went over recursion a bit more when talking about tree lists with their nodes, which could be a root, a leaf, or an internal node. The recursive code occurs when calculating the height of the tree, or the number of children or leaves a tree has. There were many terms discussed in class pertaining to trees which were interesting, but something I found even more interesting since week one was list comprehension. List comprehensions are lines of codes that are read more easily, as if like a regular English sentence, which is why I noticed it since week one of this course because we were not used to this kind of coding in CSC108. They also shorten codes of multiple lines into one by writing both the 'if' statement and the 'else' statement in one line. When I first saw this kind of coding, it confused me and took a bit of getting used to, but the lab this week aided me in reading list comprehensions as we were to rewrite them in the structure we were used to. I may need a bit more practice with this way of coding, but in the end, it should be more efficient.

An example of list comprehension:
new_lst = [x**2 for x in origin_lst if x > 0 else abs(x)]

Recursion

Last week, we began learning about recursion and were able to implement this knowledge into this week's lab. We traced methods that used recursion such as one that converted numbers to their binary representation, but we also wrote recursive methods ourselves, such as ones that freezes lists. Through these exercises, I was able to better understand what recursion is and how it works. A recursive function is one which calls upon itself within the function. This is useful when trying to execute nested loops. However, one disadvantage of recursion as I am told is that it is much slower than non-recursive function, and can cause StackOverflow. Recursion seemed complex to me because it was difficult at first tracing the functions as it entered into nested loops, but because of the exercises we practiced with in our labs, I was able to better understand recursion.

Week 4: Exceptions

In the previous week, we learned to write exception classes and try statements. We were able to implement this knowledge into this week's exercise, where we wrote our own exceptions (E2Error, E2OddError) for our try statements. I had a lot of trouble understanding the three components of a try statement and in which order they execute. Because of this, I had to do a lot of research before figuring out how to complete the exercise. This frustrated me because the examples I found online were not completely relevant to the tasks we were given, but in the end, I managed to figure it out. A try statement includes three components: try, except, and finally. The code under the try clause is executed first, and if an error is detected, it will execute the except clause of whichever error occurred. The finally clause executes whether or not an error occurs.

Another area that I had difficulty in was writing exception classes, or rather, implementing them into my except clauses; however, I was able to learn how to do this, which is why this is one of my biggest achievements this week.