Week 12: Nov 25 - Dec 1

This was the last lab of the course, and a very interesting one. The goal was to create a "complete binary tree" which is simply one where each node must be inserted in the left most spot on the tree. One implication is that all "levels" (or nodes of the same depth) must be filled except the last one, and that the entire tree can therefore be distinctly represented by a list. To parse a list into such a complete binary tree was the first part of the Lab, with the rest being creating standard tree methods (such as finding the left, right, and parent nodes given an index, and returning the inorder representation of the tree). The main trouble that my partner and I had with this lab was the left and right functions; though they returned the right index, they were not treating an incorrect index (i.e., one that does not exist within the tree) as an error, and therefore causing problems with the inorder and max_sum methods, both of which used the left and right method in order to do their jobs.

In lecture, we learned about scopes, of how global variables are defined vs local variables, as well as how the variable self, used in all methods to refer to the instance of the class containing the method, can be called other things. In addition, the concept of tracing through iterative and recursive programs was introduced, though for recursion I had already been using that method, except perhaps I traced more steps than necessary.

Week 11: Nov 18 - 24

In class, we learned about the python equivalence of encapsulation within Java: how to limit outside user interaction with the attributes of a class. This is done through the Python property command, where you can set it so that every time an attribute is called upon, this is automatically redirected to the appropriate method instead of directly returning the value of the attribute, as well as doing the same for modifying the attribute's value. Another valuable part of the property command is that you can change the name of the attribute, but as long as you keep the property command the same, the attribute can still be modified according to its previous name, as well as by accessing the new methods. This allows you to change your code will still having it be compatible with programs that implemented the old version. I found this very interesting, as I was always troubled by Python's openness, a lack of private and public keywords significantly decreased the security of the program, as any attribute was technically able to be directly modified, often leading to errors in the code if done.

In the tutorial, we continued exploring sorting algorithms, specifically calculating best case, worst case and average case scenarios for the common sorts. The one unexpected result was that bubble sort actually did worse on the nearly sorted list (which I expected was simply a list with a few elements reversed or out of order, which would have been almost the best case scenario for it, with the best one being a completely sorted list) but due to the way that the nearly sorted list was calculated, which is where the first few elements was switched with the last few, it actually made bubble sort more inefficient than a completely unsorted list. Though this could be thought of as a nearly sorted list, the reversed nearly sorted list was actually closer to the best case scenario for bubble sort simply because of how nearly sorted was calculated, a definition that I wouldn't exactly classify as nearly sorted.

Week 9: Nov 4 - 10

Assignment 2 was finished this week, an exercise in trees and a use for them. Though I coded my assignment the way that Prof. Heap suggested it to be coded (specifically with star node and dot node splitting up the string at all possible values and comparing until they get a match), I found an alternative way that may be more efficient (though I have yet to solve for two cases). This is how it goes (this occurs within a helper function that takes in a Node and a str to match, returning a tuple of bool and str):

1. If the Node is a RegexTreeNode, compare its value (either 1, 0 or e) with the first character of the string. Return True if there is a match, or False otherwise, along with the matching string with the first character removed.

2. If the Node is a RegexDotNode, call upon the helper function recursively for left and right sides, giving it the full string for the left side, then giving the left side modified string for the right side. Returns True and modified string if both sides return True, false and modified string otherwise.

3. If the Node is a RegexBarNode, do the same thing as RegexDotNode except it gives the full string for both sides, and returns True (and the respective modified string), if either side returns True.

4. If the Node is a RegexStarNode, keep on calling the function recursively until whatever is within the RegexStarNode returns False. Then return modified string and True (there is no condition that will cause a RegexStarNode to return False).

For example, when given the Regex '(1.(1|0)).0' and the string 110, the code would execute like this:

The Node is a RegexDotNode, call function recursively for left side. Function given: (1.(1|0) and string 110.

    The Node is a RegexDotNode, call function recursively for left side. Function given: 1 and string 110


        The Node is a RegexTreeNode. Match value of Node to first character of string: 1 matches 1. Removes first element and returns it, as well as True. Returns: (True, 10)

    Calls function recursively for right side of RegexDotNode. Function given: (1|0) and string 10

        The Node is a RegexBarNode. Call function recursively for left side. Function given: 1 and string 10

            The Node is a RegexTreeNode. Match value of Node to first character of string: 1 matches 1. Removes first element and returns it, as well as True. Returns: (True, 0)

        Calls function recursively for right side of RegexBarNode. Function given: 0 and string 10

            The Node is a RegexTreeNode. Match value of Node to first character of string: 0 does not match 1. Removes first element and returns it, as well as False. Returns: (False, 0)

        Since the left side is True and the right side is False, the RegexBarNode returns True and the value of the string that made it True. Returns: (True, 0)

    Since both sides of the RegexDotNode are True, the RegexDotNode returns True and the value of the string as it is returned from the right side. Returns: (True, 0)

Calls function recursively for right side of RegexDotNode. Function given: 0 and string 0

    The Node is a RegexTreeNode. Match value of Node to first character of string: 0 matches 0. Removes first element and returns it, as well as True. Returns: (True, '')

Since both sides of RegexDotNode are True, the RegexDotNode returns True and the value of the string as it is returned from the right side. Returns: (True, '')


This operation is more efficient than looking at all possible split points for RegexDotNode and StarNode, especially for longer strings, but has two cases in which it fails (though a solution is quite possible, I did not think of one for the assignment due date). The first case is one in which both sides of the RegexBarNode return True, but only one would work (like if it was (1|(1.0).1 and the string was 101), there was no way of calculating easily which side of the RegexBarNode to return. The second case is when the RegexStarNode satisfies the same conditions as the right side of the RegexDotNode (for example, (1|0)*.1 would fail for all strings ending with 1 with the current implementation, as the RegexStarNode code would remove the entire string and not leave a 1 to satisfy the RegexDotNode). These problems I believe I can solve given time however.


In terms of the lectures, sorting algorithms and time complexity was the subject of this week. It was very interesting learning about the different types of "big-oh" complexities, and how they vary throughout the different sorting algorithms, as well as how efficient the python sorting algorithm is and how it's programmed that way. As the exam is next week, I do not have much time to extensively make an entry about the lab this week, but it was a very interesting exploration into converting a tree into a list, we converted strings (and by extension lists) into trees for previous exercises and assignment 2, this is actually the first time we convert a tree back into a list, specifically a linked l

Week 8: Oct 28 - Nov 3

This week the class explored one of the uses of a tree: a binary search tree. By putting all values below the root node as the left subtree, and all the values greater as the right subtree, a binary search can be performed much more efficiently than if the values were simply in a sorted list (you would still have to constantly find the middle value in a sorted list). Of course, there is the added complexity of actually adding the values into a binary search tree, but assuming that you start from an unsorted list, it should take around the same time to add values into a tree from a list as it is to sort the list. All of the binary search trees were constructed using linked nodes, the concept of which was explored last week.

The lab and exercise this week both demonstrated how binary trees work. Though the process of searching through and inserting elements into a binary tree, as well as other operations such as finding all values less than a given value (which was the topic of the lab) are all best done recursively, step 4 of the lab demonstrated that, by using a stack data structure to store nodes, it is possible, though much more difficult, to create an iterative way of searching through a binary search tree. The exercise, though simple (most of the code required is given, and only about 5 lines were added in both part A and B), it reinforced the way that a binary tree operated.

Oct 21 - 27

Linked lists and assignment 2 were the main topics for this week, both of which were very interesting. A linked list is not really a list in the strictest sense, it is more a recursive data structure: the entire list is contained within the root node of the tree. Each node has two attributes, its value and the next node. Thus, the only reference needed to the list is one to the root node, with the danger that if this node was at any instance not referenced to, the entire list would be destroyed by garbage collection within Python.

A linked list is to be used in binary tree form for assignment 2, which requires the parsing of a regular expression into a binary tree. My group has already finished step 1, but step 2 proposes some difficulties, especially the star node, which would possibly require comparing every possible combination of it to the matching string, and bar node, in some very specific cases.

Week 6: Oct 14 - 20

This week was the Midterm for 148, as well as an exploration of trees, data structures that are organized recursively. Due to its recursive nature, trees are best created and read recursively, although they can be converted back to lists using three methods (which create lists with the same elements but in different order): preorder, inorder and postorder. These methods are known as traversal methods and are ways to step through all nodes once each, using only the connections between parent and children nodes. Though at first I didn't know of why anyone would prefer using a data structure such as a tree over just a regular list, I learned many applications for trees this week.

One of the best uses of a tree is to search for values, as demonstrated earlier in an exercise. By making sure that one branch of the tree is larger than the root node, and the other smaller, you can significantly speed up the search process, as long as converting the initial set of values into such a tree is efficient enough.

Object Oriented Programming

One of the major advancements of programming languages, object orientation really allows development of a programming language outside of initial development. Rather than a long list of commands, supplemented occasionally with functions to reduce repetition, object oriented programming allows for the bundling of functions and variables these functions operate on into objects, and therefore programming in an object oriented can be seen as creating interactions between objects rather than the data itself. This additional layer of objects allows the programmer to not only reuse methods that he has created with the attributes that he has created with them, it also allows him to use other people's objects. The additional level of privacy and security offered by the object system allows this to a degree simply using functions cannot. Thus, with the development of object oriented programming, the world of programming was taken to a whole new level.