Week 10 – Assignment 2 Part 2

For the second part of Assignment 2, we had to implement four functions that performed operations on regex tree strings, ternary strings, or RegexTree objects.

I think the hardest part by far was finding the outermost root of binary trees for is_regex and build_regex_tree. When I first wrote it, I'd tried to find the root by using the built-in index function. My function involved finding the index of the rightmost ')' between the beginning of the string and r2's first '('. If r2 doesn't contain a '(', then just find the last ')' in the string. The index after that is the “root_index”. However, if there isn't any ')' in the string, then I just set the “root_index” as 1 as it should be right after the first item. Finally, I increased the index by 1 for every '*' in the string.

This was not one of the methods that the professor hinted to us in class, but I came to this conclusion on my own and it worked...although it's admittedly a very messy solution. In the end, my partner came up with a much better solution, where she simply found the indices of every '.' and '|' in the string. Then, if the difference between the '('s and ')'s before this index was equal to 1, then she knew that this was the outermost root index. The code for this method was, indeed, much shorter and more concise, so we went with this in the end. It was also one of the methods that the professor had suggested, but I hadn't understood it in class, so seeing my partner's code was very helpful to me.

Week 9 – Lab #8 and Exercise 3

This week's lab was better than last week's, at least for the first two BST_rec modules that we had to implement. But then we had to implement one method in the BST class and another in the _BSTNode class, and a third in the _BSTNone class, and I got kind of confused on what I should be calling. I couldn't figure out what would be different with the count_less in _BSTNone at first. In the end I realized that since every None in BST is represented by _BSTNone, and that class has a count_less method, I didn't have to write the “if...else” conditions because they would be taken care of by the methods of the different types of BSTNodes.

As for our third exercise, all I can say is that I did a lot of tracing for these functions to understand how the program should work.

For part a, I took a tree's preorder and inorder traversals, broke them down into left and right subtrees (while noting how I knew which part was the left, root, and right), and got the pre- and inorders of these subtrees, then repeated until I got to an empty tree, at which point I could backtrack and substitute a None into the new tree being made. I made several trees this way to make sure that my method of splitting the traversals was correct, then wrote the function according to how I'd done it while tracing. Then I traced through my function several times to make sure it was correct.

For part b I think that my code is longer than it needs to be, but also that it's quite clear. You could say that I had some trouble with this part; it took me at least two hours just to grasp the recursive nature of this problem, trying to understand and make use of the hint. But at one point something clicked and I proceeded to finish the function in another hour. It was that I needed to find the child with the deepest leaf. This seemed a lot more obvious after I realized it, but...well, of course. So with that, I recursively called the function on the left child (if there was no right child) or the right child (if there was no left child) or cal it on both children (if they exist) and find the one with the maximum depth and return that. 

Week 8 – Lab #7 and Assignment 2 Part 1

I think this lab was the first that I found quite difficult, aside from maybe the second one. I thought I'd understood the linked list structure, but when doing this lab, I had a lot of trouble coming up with the solutions. For instance, for the __setitem__, __delitem__, and insert methods, I didn't know how to find the position and modify the item at that position. I kept thinking of using the __getitem__ method to find the item at the given index, but then realized that I couldn't do anything with the returned value because it was just a value, not an attribute that I could set to modify the list.

def __setitem__(self, ind, val):
     if self.empty or ind < 0:

         raise IndexError

     else:

          self.__getitem__(ind) = val

But I did realize that this would not work, and I knew I should've been using recursion, but...I couldn't think of a way to do it. After some help from the T.A. I mostly got that we could keep checking a smaller and smaller portion of the list and somehow, at the end, when the index in question is the beginning of the list, it would be the item attribute of the LinkedList and we can set it as so. I'm currently still trying to understand this better.

As for Assignment 2, well, this was quite a confusing concept. It took me a long time to understand what we were “designing”, and then what we had to write and did not have to write for this section. After figuring out that we just had to create classes for the different types of RegexTrees and implement their attributes, it was easier to get started. However, I wasn't so sure about the inheritance choices that I made, because I think I still had some repeated code. I also used BarTree's __init__method in my DotTree class, which probably wasn't the best idea now that I think about it, but I didn't know how to get rid of that bit of duplicate code. All in all, I didn't find it too difficult to write but I was quite unsure of the design choices that I made.