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!