Oct 27 2013

Oct 27 2013

I am rather ashamed to admit that I forgot to post entries last week. Therefore, this week's entry is going to cover the materials from this week and the week before.

First, let us take a look at the course material. Recursive data structures are highly useful not only in storing values at nodes and leaves, but can also be used to model biological or engineering branching processes. The mastery of the binary (OR general) tree structure can be highly beneficial when it is necessary to extract values and perform practical calculations from such models. For instance, consider a single yeast in vivo and we are interested in learning about the asexual reproduction of such organism. First, we are informed that a particular yeast has a probability of survival of 1/3. If it survives, it reproduces two off springs with the identical probability of survival. This is a classic example of branching process. Although the data (0 for death 1 for survival) can be stored in terms of a binary tree, it has the added complication that the data at a current node is completely determined by the data from the previous node. There are many interesting calculation that can be performed with this particular problem and I will look into it further in the following week.

In terms of linked structures, I have learned that one of the advantages of such data structure is that not only each node is linked to the next through the . next attribute. It also assigns each node to a different location in memory. If such linked structure is a list, than such lists can be used to perform numerical integration with high accuracy since the area of each partition of a given function can be stored in a different memory location. This means that if the numerical value of an area is relatively large or cannot be expressed in rational form, one can obtain more accurate data since more memory will be available.

After looking into the applications of this week's lecture material, let's now take a look at this week's assignment and the test. While doing this week's assignment and as well as last week's, I have encountered the difficulty of obtaining information in linear form from a tree structure. The cause of such problem is mainly due to the recursive nature of the data structure. After many hours of struggle , I have eventually grasped the general approach in solving such problems. First, we must recognize the desired result as a linear data type. That is, a data type with no recursion and can be successfully obtained through the linear combination of different partitions of the original data. And the only other thing that is needed to be accomplished is to write a linear combination of recursive functions. The number of distinct elements in this linear combination depends on the actual structure of the tree. However, if a binary tree is present, than such formula contains three distinct element. One for the stopping case, another for the right node and another for the left. Looking at a more concrete example taken from Professor Heap's Work:

def preorder(tl: 'TreeList') -> list:
    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2])) (Heap, 2013)

In here we can see that the stopping case is actually [] if t1 is None, but we can also see that the recursive functions on t1[1] and t1[2] are written as a linear combination. This eventually creates a single list contains the data from a tree. What is originally in recursive form are broken into linear form due to the nature of the addition binary operation. With similar above approach, I was able to solve the problem in this week's exercise with the following code:

def find_internals(self):
        if self.left or self.right is not None:
            A = [self.item] + ([] if self.right is None else
                               self.right.find_internals()) + \
                ([] if self.left is None else self.left.find_internals()) 
        else:
            A = []
        return A
   
    def find_leaves(self):
        if self.left or self.right is not None:
            B = [] + ([] if self.right is None else self.right.find_leaves()) \
                + ([] if self.left is None else self.left.find_leaves())
        else:
            B = [self.item]
        return B
   
    def leaves_and_internals(self):
        return (self.find_leaves(), self.find_internals())

Although the above code can be even further simplified. The main accomplishment in the code is that it was able to solve the problem with a systematic approach. Notice the similarities in the helper function code and professor Heap's code, the idea of linear combination of recursive functions can solve a wide range of problems that demands a linear structure as a result.

Now about the test, I have not perform as well as I expected in this test. Part of the reason might be the fact that this was the first computer science test tat I have taken. But the main reason is due to the fact that I have made some careless mistakes while using list comprehensions to answer question 2 and 3. One thing that I have learned from this test is that when using list comprehensions, we must pay attention to the type of the data we have on hand. For instance, let A=[], A.append(0) itself is actually a None type while A is still a list. This means that if the altered A is the desired final result, the returned value should be A.

In summary, I have found the last two weeks of CSC148 very informative and beneficial. The material covered are very practical and the exercises provide a good practice with recursive data structures. Although I do not find the course material to be challenging, but I don find that it takes sometime to get use to. In the following week, I intend to practice more on recursive data structures by looking into their practical applications and perform some of those calculations and it is my hope that through sufficient practice, my performance on the next midterm can be improved.