Week 12 - review of implementing LinkedList by using LListNode

class LListNode:
    """Node to be used in linked list"""
   
    def __init__(self: 'LListNode', value: object,
                 nxt: 'LListNode' =None) -> None:
        """Create a new LListNode containing value and with next node nxt

        nxt --- None if and only if we are on the last node
        value --- always a Python object, there are no empty nodes       
        """
        self.value, self.nxt = value, nxt

class LinkedList:
    """Collection of LListNodes"""

    def __init__(self: 'LinkedList') -> None:
        """Create an empty LinkedList"""
        self.front = None
        self.size = 0

    def insert(self: 'LinkedList', value: object) -> None:
        """Insert LListNode with value at front of self

        self.front = LListNode(value, self.front)
        self.size += 1
This is the last week of CSC148. I tend to focus on reviewing the LinkedList in this week. It is important within LinkedList or even Queue, Stack that we use another class to store the data instead of standard containor when we want to modify the LinkedList. I illustrate 2 classes above. Takes this for example, we creat a new LinkedList named b = LinkedList(). Then we want to add one item on b. we call the method "b.assert(1)". Then we get b == LinkedList(1, LinkedList()). How does the method make this happen? Okay, I wil explain it here. Basically, we have an empty LinkedList which is b. And b.front is equal to None, size is equal to 0. Then we assert 1 into the LinkedList. The method insert is called. This method calls the LListNode class and creat a new LListNode. The new LListNode's value is replace the item directly and nxt is replaced by the original LListNode. So we get b == LinkedList(1, LinkedList()).

Week 11 - Sorting and Efficiency

This week we have learned about different sorting algorithm, and compare their run time by inputting random same size elements. In this blog, I will illustrate my understanding on each of those sorting algorithm's characters.

As for bubble sort, it is considered as a most inefficient sorted algorithm because it needs to go through the whole unsorted part. For example, if a list has length n, then the worst case of bubble sort  have to exchange n-1 times passes. When it is random order list, the items will be exchanged until the last position is known. Besides, the most important thing within the bubble sort is to keep tracking specific element, where we can see from the function code. For instance, "temp = alist[i], alist[i] = alist[i+1], alist[i+1] = temp", the code here using index to keep track of element will be sorting. Then it compares each pair until finish this pass. For every pass, it takes a bit more time. Therefore, this sorting method will execute in a longer time obviously than other sorting method if the list is big enough.The run time of worst case of each sorting method is list in below chart.

There is another sort algorithm quite interesting, which is Merge sort. Basically, it uses recursion to help itself to keep separate the list into two parts until the length of sub-list not bigger than one. Then the function will start comparing items by pair. The pair is represented by left part and right part. It will put the bigger element into left and smaller into right. The list does not matter contains odd number element or even number element. Because the while loop of  length statement will differ it, such as "while i<len(lefthalf) and j<len(righthalf):". In addiction, we can conclude from that char that Merge sort is more efficient than Bubble sort, with 0.4s less.

Moreover, I want to show result that I got from the lab 10, which illustrate directly the run time of each function. The chart in the below show the relationship between input size and run time when using different sorting algorithm.

week 10 LinkedList

Linklist contains basically has two elements, the first one is an number, another one is a new Linklist. I think it is similar to the tree structure. Every single Linklist contains a node, and it connect to another Linklist. Within the Linklist, we need to use recursion when we need to get access to some specific elements. For example, we need to change or insert a number in location 10. Then we set up a = 10, the execute process start from the very out side. And then as long as the second element is a Linklist, it goes into next level, and a -1. We recur this step until a = 0, so that we can change or insert a number into that location.

A linked list can be understood in terms of another linked data structure, the binary tree. In a binary tree, each node contains a value, and two children, which themselves are either binary trees or “leaf nodes”. As the tree metaphor would suggest, leaf nodes are the “ends” of the tree which are just single values.

class LinkedList:

"""Linked list class"""

def __init__(self: 'LinkedList', item: object=None,

rest: 'LinkedList'=None) -> None:

"""Create a new LinkedList

item - The first element of the linked list,

Not present if self will be the empty linked list.

rest - The linked list that contains the elements after item.

Not present if self will be the empty linked list."""

self.empty = (item is None) and (rest is None)

if not self.empty:

self.item = item

if rest is None:

self.rest = LinkedList()

else:

self.rest = rest

I want to illustrate the initialized method of LinkedList. Firstly, the method takes 2 parameters. They are item and rest. Then, we creat the variable by setting self.item = item and self.rest = rest. This is the basic structure of LinkedList. After that we can use prepend method

def prepend(self: 'LinkedList', item: object) -> None:

"""Add new item to front of self

>>> lnk = LinkedList()

>>> lnk.prepend(7)

>>> lnk.item == 7

True

"""

self.item, self.rest, self.empty = item, copy(self), False

to add a new link to the original LinkedList. If we want to get access to some specific item. We can use recursion to get access. For example, we want to get the item in position 4. Then set n = 4, we set n - 1 when we go into the rest of LinkedList. We recur this step until n = 0. Then we return LinkedList.item.

Week 9 - Binary Tree

During the lecture, we learn a new concept name Binary Search Tree. The tree is a list. And it base on a class structure. There are three elements within BST. The first one is the root, which is the first element of the BST. The element follow the root is the left node. A binary tree is a tree-like structure that has a root and in which each vertex has no more than two children.

 Each child of a vertex is called a left or right child. Implementing a binary tree can be complex. The code below shows a simple implementation using a Tree Class. The first few methods have been implemented. There are three ways of traversing a binary tree: pre-order, in-order and post-order.

For the pre-oeder and in-order, The below function is what is write about it:

def make_tree(preorder: list, inorder: list) -> list:

    """Return a TreeList containing the binary tree whose pre-order and

       in-order traversal lists are given asargument.

   

    >>> make_tree([],[])

    >>> None

   

    >>> make_tree([5, 4, 6, 7, 3, 1, 2], [6, 4, 7, 5, 1, 3, 2])

    [5, [4, [6, None, None], [7, None, None]], [3, [1, None, None], [2,

    None, None]]]

    """

   

    a = 0

    b = 0

    c = []

    d = []

    e = []

    f = []

   

    if len(preorder) >= 3:

        for x in range(len(inorder)):

            if inorder[x] == preorder[0]:

                a += inorder[x - 1]

                for y in inorder[:x]:

                    c.append(y)  # 6 4 7

                for z in inorder[x + 1:]:

                    d.append(z)  # 2 3 1

        for y in range(len(preorder)):

            if preorder[y] == a:

                b += preorder[y + 1]  # 3

                for i in preorder[1:y + 1]:

                    e.append(i)  # 4 6 7

                for z in preorder[y + 1:]:

                    f.append(z)  # 3 2 1

        return [preorder[0], make_tree(e, c), make_tree(f, d)]

   

    elif len(preorder) == 2:

        if preorder == inorder:

            return [preorder[0], [[preorder[1], None, None], None]]

        else:

            return [preorder[0], None, [[preorder[1], None, None]]]

       

    elif len(preorder) == 1:

        return [preorder[0], None, None]

   

    else:

        return print(None)

Week 8 - Linklist

Linklist contains basically has two elements, the first one is an number, another one is a new Linklist. I think it is similar to the tree structure. Every single Linklist contains a node, and it connect to another Linklist. Within the Linklist, we need to use recursion when we need to get access to some specific elements. For example, we need to change or insert a number in location 10. Then we set up a = 10, the execute process start from the very out side. And then as long as the second element is a Linklist, it goes into next level, and a -1. We recur this step until a = 0, so that we can change or insert a number into that location.

Week 7 - Recursion II

Recursion is a useful way to deal with the complex problem.  Recursive functions will have two basic components. First, a "base case" which tells the computer what to do once a certain condition is met, and seconds, a "recursive step" where the function calls itself.At the very beginning, it was so hard for me to understand the structure of recursive function body. What makes me confuse is that 'How can function call itself when the function body is not completed'. This point makes me struggle for a long time before I get used to it. The recursive way from my current understanding is that we go into the parameter from the deepest level and then go out step by step. Within the function body, we usually use the if statement to determine whether we need to recur again or return something. For this most important part during this semester in 148 courses, practice is the best way to across the challenge.

Week 5 - Class

This week we just finish our A1. The most important challenge  part of this assignment is class design. It has a higher requirement for class design.  Class structure is made by initialize method, and other  methods. The initialize method is used to assign the parameter  and keep track of that value through the whole class. During the first assignment, the task is to move the cheese from original stool to the destination stool. Our group implement two main help functions in the class. The first one is a help function and it moves three cheeses from original stool to destination stool within three stools. Another help function is to move three cheeses from original stool to destination stool within four stools. There are only three parameters that are  needed in the function. The first two that are typed by the player. Another is transfer stool, which we do not know. Thus, we assign the stool is transfer stool as long as the stool is empty or the top cheese of original stool is smaller than top cheese of transfer stool.