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!