Week11 SLOG: Wrong understanding on Linked List

After revisiting week 8 and week 9 SLOGs, I found I made something wrong with Linked List. In these two SLOGs, I defined some concepts about Tree and Linked List and wrote some functions about them. However, I did not understand the concept about Linked List clearly because I did not consider Linked List as one kind of Tree Type.

First of all, I need to review definition of Linked List and Tree to prove what I made wrong with Linked List. Firstly, a Tree is a set of nodes with directed edges between some pair of nodes and an edge connects a parent node and a child node. Secondly, a Linked List is a linear sequence of nodes and we will keep a reference to the front of the sequence. In conclusion, Linked List can be considered as a tree like this (assuming Linked List has 6 nodes in this Tree):

 16

 ↓

 15

 ↓

 14

 ↓

 13

 ↓

 12

 ↓

 11

Each height of the tree only contains one node, and it is the maximum height that a tree can have. In addition, there is only one path that the tree has, which likes a linear sequence. Overall, Linked List is a type of tree.

Week10 SLOG: mutate Insert and Delete function

In this week, I have learned something about mutating functions like insert and delete in Binary Search Tree.

First of all, I need to define class BTNode and BST. And I also need to initialize them.

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

Class BST:

'''Binary Search Tree node.'''

def __init__(self, root=None):

    '''(BST, BTNode or None) -> Nonetype

    Create BST with BTNode root.

    '''

    Self.root = root

Next, I mutate insert and delete methods.

def insert(node, data):

    ''' (BTNode, object) -> BTNode

    Insert data in BST rooted at node if necessary, and return new root.

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> print(b)

            14

        12

            10

    8

            6

        4

            2

    <BLANKLINE>

    '''

    return_node = node

    if not node:

        return_node = BTNode(data)

    elif data < node.data:

        node.left = insert(node.left, data)

    elif data > node.data:

        node.right = insert(node.right, data)

    else:  # nothing to do

        pass

    return return_node

def delete(node, data):

    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> b = delete(b, 12)

    >>> print(b)

            14

        10

    8

            6

        4

            2

    <BLANKLINE>

    '''

    if not node:

        pass

    elif data < node.data:

        node.left = delete(node.left, data)

    elif data > node.data:

        node.right = delete(node.right, data)

    elif not node.left:

        return_node = node.right

    elif not node.right:

        return_node = node.left

    else:

        node.data = _find_max(node.left).data

        node.left = delete(node.left, node.data)

    return return_node

Week 8 SLOG: Linked List

From the last week lectures, I learned something about linked list. 

Initially, a linked list is a linear sequence of nodes and we will keep a reference to the front of the sequence. Furthermore, in the lecture, we define two different classes which are LLNode and LinkedList. LLNode represents a single node and LinkedList represents the linked list as a whole.

First of all, we need to define LLNode class, including __init__, __str__ and __eq__ methods:

class LLNode:

     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

    def __str__(self):

        ''' (LLNode) -> str

        Return a user-friendly representation of this LLNode.

        >>> n = LLNode(4, LLNode(6))
        >>> print(n)
        4 -> 6 ->|
        '''
        if self.nxt is None:
            return '{} ->|'.format(str(self.value))
        else:
            return '{} -> {}'.format(str(self.value), str(self.nxt))

 def __eq__(self, other):

        ''' (LLNode, object) -> bool

        Return whether LLNode (self) is equivalent to other.

        >>> LLNode(3).__eq__(3)
        False
        >>> n = LLNode(4, LLNode(6))
        >>> n2 = LLNode(4, LLNode(6, None))
        >>> n.__eq__(n2)
        True
        '''
        return (type(self) == type(other) and
                (self.value, self.nxt) == (other.value, other.nxt))

And then we go to define the LinkedList class,  including __init__, __str__, __eq__  and prepend methods:

class LinkedList:
    def __init__(self):
        ''' (LinkedList) -> NoneType

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

    def __str__(self):
        ''' (LinkedList) -> str

        Return a human-friendly string representation of
        LinkedList (self)

        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> print(lnk)
        5 ->|
        '''
        return str(self.front)

    def __eq__(self, other):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) is equivalent to
        other.

        >>> LinkedList().__eq__(None)
        False
        >>> lnk = LinkedList()
        >>> lnk.prepend(4)
        >>> lnk2 = LinkedList()
        >>> lnk2.prepend(4)
        >>> lnk.__eq__(lnk2)
        True
        '''
        return (type(self) == type(other) and
                (self.size, self.front) == (other.size, other.front))


    def prepend(self, value):
        ''' (LinkedList, object) -> Nonetype

        Insert value at front of LLNode (self).

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> str(lnk.front)
        '2 -> 1 -> 0 ->|'
        >>> lnk.size
        3
        '''
        self.front = LLNode(value, self.front)
        if self.back is None:
            self.back = self.front
        self.size += 1

Week 8 SLOG：the Summary of Tree

Tree is an abstract data type. First of all, a tree is a set of nodes with directed edges between some pair of nodes and an edge connects a parent node and a child node. Following this, the path is a sequence of nodes n1, n2...nk where there is an edge from ni to ni+1 and the length of a path is the number of edges on it. 

In addition, it has many different parts such as leaf, internal node, subtree, height and depth.  Firstly, leaf is a node with no child. Secondly, internal node is a node with one or more children. Thirdly, subtree is a tree formed by any nodes and its descendants, and the edges connecting them. Fourthly, height is the maximum path length +1. Finally, depth equals to height of the whole tree minus the height of the tree rooted at that rode.

Initializing the class Tree:

class Tree:
    ''' Represent a Bare-bones Tree ADT'''

    def __init__(self, value=None, children=None):
        ''' (Tree, object, list) -> NoneType

        Create Tree(self) with content value and 0 or more children.
        '''

        self.value = value

        self.children = children.copy() if children else []

For the height of the tree, here is the code of it:

def height(t):
    ''' (Tree) -> int
    
    Return height of Tree t,

    >>> tn2 = Tree(2, [Tree(4), Tree(5), Tree(7), Tree(8)])
    >>> tn3 = Tree(3, [Tree(6), Tree(10)])
    >>> tn1 = Tree(1, [tn2, tn3])
    >>> height(tn1)
    3
    '''
    if not t.children:
        return 1
    else:
        return max([height(c) for c in t.children]) + 1

Furthermore, we can also analyze the tree from different sides, so we initializing the class BTNode:

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

And here is the method of parenthesize:
def parenthesize(b):
    ''' (BTNode) -> str

    Parenthesize the expression rooted at b, so that float data is not parenthesized,
    but each pair of expressions joined by an operator are parenthesized.

    Assume:  -- b is a binary tree
             -- interior nodes contain data in {'+', '-', '*', '/'}
             -- interior nodes always have two children
             -- leaves contain float data

    >>> b = BTNode(3.0)
    >>> print(parenthesize(b))
    3.0
    >>> b = BTNode('+', BTNode('*', BTNode(3.0), BTNode(4.0)), BTNode(7.0))
    >>> print(parenthesize(b))
    ((3.0*4.0)+7.0)
    '''
    if b.right is None and b.left is None:
        return b.data
    else:
        return ("(" + str(parenthesize(b.left)) + b.data 
                + str(parenthesize(b.right)) + ")")

What's more, below is the method to find the longest path in the tree:

def list_longest_path(node):
    ''' (BTNode) -> list

    List the data in a longest path of node.

    >>> list_longest_path(None)
    []
    >>> list_longest_path(BTNode(5))
    [5]
    >>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7)))
    [5, 3, 2]
    '''
    if node is None:
        return []
    else:
        if node.left is None and not node.right is None:
            return [node.data] + list_longest_path(node.right)
        elif node.left is None and node.right is None:
            return [node.data]
        elif node.right is None and not node.left is None:
            return [node.data] + list_longest_path(node.left)
        else:
            left = list_longest_path(node.left)
            right = list_longest_path(node.right)
            if len(left) < len(right):
                return [node.data] + right
            else:
                return [node.data] + left

Week 7 SLOG: Summary of Stack

In the lecture, I learned an abstract data type which is Stack. It is a last-in-first-out structure and there are some methods like pop, push, is_empty in its class.

First of all, in the Stack class, I need to initialize the stack to be empty.

class Stack:

def __init__(self):
    """

    (Stack) -> NoneType

    Initialize this Stack to be empty.

    >>> isinstance(Stack(), Stack)
    True
    """

    self.data = []

And then, I can create a method called push which can put object x on top of the Stack.

def push(self, x):
    """ 

    (Stack, object) -> NoneType

    Place object x on top of this Stack.

    """

    self.data.append(x)

Next, I can create a method called pop which can remove and return the top item in this Stack.

def pop(self):
    """
    (Stack) -> object

    Remove and return the top item from this Stack.

    >>> s = Stack()
    >>> s.push(1)
    >>> s.push(5)
    >>> s.pop()
    5

    """

    return self.data.pop()

Concluding two methods pop and push, it is easy to find this Stack is a last-in-first-out structure. Finally, I can create a method called is_empty to check whether the stack is empty.

def is_empty(self):
    """ 
    (Stack) -> bool

    Return whether this Stack is empty.

    >>> s = Stack()
    >>> s.push(1)
    >>> s.push(5)
    >>> s.pop()
    5

    >>> s.pop()

    1

    >>> s.is_empty()

    True

    """

    return self.data == []

Overall, if running this Stack, the object in this Stack will be put on the top of Stack and it is also removed out first. Therefore, it is an abstract data type with a last-in-first-out structure.

Week 6: Summary of Object-Oriented Programming concepts

    In the Object-Oriented Programming, there are many concepts which are class, object, message passing, inheritance, encapsulation, polymorphism and abstraction.
    Firstly, class defines the abstract characteristics of a thing, which means that class defines general property of that thing and what it can do. And the methods in the class can be called the member of that class. Secondly, object means the specific things like some examples in the class. Thirdly, message passing indicates that an object achieves some functions by receiving message, processing message，passing out message or other methods. Fourthly, a class usually has some subclass which is more specific to embody himself and all subclass have the property that the class defines, which is the inheritance of the class. Fifthly, Object-Oriented Programming has encapsulation which means it hides a method of concrete steps, replaced by transmitting message through message passing. Encapsulation is only a particular class of objects can be accessed by members of the particular class restrictions and they often use interface inbound and outbound messages.Sixth, polymorphism indicates that different classes related by inheritance produced its target for the same massage will make different responses. Finally, abstraction is the way to simplify the complicated problem in the reality. It can find a suitable class for specific problems and the suitable subclass to explain problems.
    Overall, Object-Oriented Programming can be seen as the program that contains a variety of independent and co-ordination objects.
    

Week 5 SLOG for tracing Recursion

Again, here is some recursion exercises I have done before:

def count_lists(L):
    '''(list or non-list) -> int

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

    if isinstance(L, list):

        return 1 + sum([count_lists(x) for x in L])
    else: # L is not a list
        return 0

1)Trace([2, 1, 3])

Answer: 1

Because there is only one list which is himself, and the elements in the list are non-list. Therefore, it returns (1 + sum[0, 0, 0]) which is 1.

2)Trace([2, 1, 3, '[4]'])

Answer: 1

'[4]' is not a list so it returns (1 + sum[0, 0, 0, 0]) which is 1, like above one.

3)Trace([7, [2, 1, [3, 4], 5], 9, [3, 2, 4]])

Answer: 4 

Because there are 4 lists, it returns (1 + 1 + 1 + 1 + sum[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) which is 4.

Here is the other one example：

def count_all(L):
    '''(list or non-list) -> int

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

    if isinstance(L, list):

        return 1 + sum([count_all(x) for x in L])
    else: # L is not a list
        return 1

1)Trace([2, 1, 3])
Answer: 4

According to the code, I know that if L is a list then it returns 1 + sum(elements in L), and if the element in L is also a list then it will run again like 1 + sum(a in element).If the element is not a list, then it returns 1.

So [2, 1, 3] is only one list which is himself. Then it returns 1 + sum([1, 1, 1]) which is 4.

2)Trace([2, 1, 3, [4]])
Answer: 6

[2, 1, 3, [4]] has two lists, then it returns 1 + 1 + sum([1, 1, 1, 1]) which is 6

3)Trace([7, [2, 1, [3, 4], 5], 9, [3, 2, 4]])
Answer: 14 

[7, [2, 1, [3, 4], 5], 9, [3, 2, 4]] has 4 lists, then it returns 1 + 1 + 1 + 1 + sum([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) which is 14.

After some exercises, I find it is easy to trace recursion if I understand the codes and I know how it works. :)