Slog of eighth week

The lecture this week talked about the information of the term test and class binary search node.

class BTNode:     ’’’Binary Tree node.’’’

    def __init__(self, data, left=None, right=None):         ’’’ (BTNode, object, BTNode, BTNode) -> NoneType

        Create BTNode (self) with data         and children left and right.         ’’’         self.data, self.left, self.right = data, left, right

If I want to insert a data in a BTNode, I need to be carful about the condition that the BTNode is none. If it is none, then the function needs to return a new BTNode with the data I want to insert. If the BTNode is not none, I will meet 3 conditions. The data is bigger, smaller than the data in the BTNode or equal to the data in the BTNode. When it is bigger, I let the right side to do the recursion. When it is smaller, I let the left side to do the recursion. When it is the same, I won't do anything.

slog of seventh week

This week, the topic we learned about was class  LLNode, to represent linked list nodes, and class LinkedList, to represent an entire linked list. This Node is somewhat similar with the node class we have learnt before. The code of those two class is following:

class LLNode:
    ’’’Node to be used in linked list

    nxt: LLNode -- next node
                   None iff we’re at end of list

    value: object --- data for current node
    ’’’

    def __init__(self, value, nxt=None):
        ’’’ (LLNode, object, LLNode) -> NoneType

        Create LLNode (self) with data value and successor nxt.
        ’’’
        self.value, self.nxt = value, nxt

 class LinkedList:

    ’’’Collection of LLNodes

    front: LLNode -- front of list
    back:  LLNode -- back of list’’’

    def __init__(self):
        ’’’ (LinkedList) -> NoneType

        Create an empty linked list.
        ’’’
        self.front, self.back = None, None
        self.size = 0

The process of LL looks like the process of  bubble sort. We need to use the while loop to control the program to find the node that we want to delete or insert.

We don't have lab this week since the strike. 

Summary of recursion

In the pass 4 week, i have learned a lot of knowledge about recursion, which is totally new to me.

What I learned first to get knowledge of recursion was about tracing the recursion. In the lab 3, i was given some functions. Here is the Example,

def count_elements(L):
    ’’’(list or non-list) -> int

    Return 1 if L is a non-list, or number of non-list elements in
    possibly-nested list L.

    Assume: L is any Python object.

    # examples omitted!
    ’’’
    if isinstance(L, list):

        return sum([count_elements(x) for x in L])
    else: # if L is not a list, count it

return 1 

When i want to trace  count elements([7, [2, 1, 3], 9, [3, 2, 4]]), the first thing I need to do is to deal with the basic list. The basic list is [7, [2, 1, 3], 9, [3, 2, 4]. After the first step, what we get is sum(1,count_elements([2,1,3]),1,count_elements([3,2,4]). And then , after the step tracing, what we can get is sum(1,sum(1,1,1),1,sum(1,1,1)). Finally, we get sum(1,3,1,3) = 8.. As i described, this is how recursion work. Unlike the function i learned in the pass, the recursion function will recall itself once and once again.

After learning how does recursion work, i study to learn how to write a recursion function, which is hard for me.
We studied how to write the recursion function by introducing Tree and BTnode.
For example, in the quiz5, I need to count the internal nodes of a tree, Tree(17,[tree(2)[tree(5),tree(6),tree(7)],tree(3)[tree(8),tree(9)],tree4)
This tree is look like that,
                17
2               3             4
567           89
As we can see, the num of internal node is 3. They are 2, 3, 17.
In order to write the recursion, i was told by the TA that, i need to study by the basic example.
The basic example is Tree(17), which have no children so that it is not a internal node. So, is a tree have no children, the function will return 0. How thing goes when we get Tree(17, [tree2])? This tree have one children, and the function will return 1. What about a tree likeTree(17,[tree(2)[tree(5),tree(6),tree(7)],tree(3)[tree(8),tree(9)],tree4). Every time we get a node, we will count 1. The function should be something like . 1+***(function(x) for x in tree.chirdren). And we know there are node in the children of the basic tree, then we need to calculate the sum of them. So the function will be 1+sum(function(x) for x in tree.chirdren)
So, when it comes to how to write a recursion function, the most important thing is the basic example. After doing that, it will be much easy to write the function.