Don't look back in anger!

One more week! Only one more week is ahead of me. Can't believe this term is almost over. Time flies. I haven't fully understood all the materials we've covered, but the end is coming. I'm having mixed feeling of relief, excitement, regret, disappointment and anger. I'm relieved and excited cause the term is almost over and I can finally have some piece in my mind. But at the same time, I regret that I didn't work harder and disappoint and angry at myself cause I didn't achieve the level I planned at the beginning of the term.

However, while I was reading my past posts again, I looked back again and calm myself down from frustration. I could tell it wasn't super easy course for me, but I did try to do some work. Also, I found many resources that I can use for my study and my understanding of materials is definitely better than before.

Well, I don't have anything to agree or disagree to my previous posts. My blog is mostly to record the stuff that I learned and to help my memory and understanding. It might be perfect, but I hope some of the information that I linked would be helpful to whoever come across my blog as they were good resources for me.

I also browsed some of the blogs of the other students. I didn't check every single blog(unfortunately and of course,) instead I was scrolling down and click simultaneously then I can choose random blogs. I've seen some blogs similar to mine, or shorter, loger and even empty one. Many of students were working hard on this course on their own way. Some of the blogs that I visited were very intuitive and motivated.

Here are two of the blogs that I really like:

http://computersciencebysystemupdates.blogspot.ca/
This blogger writes very intuitive posts. His summary of Object-Oriented Programming was very well-organized. Also the one with the drawing beautiful fractal using turtles was amazing and motivated me to mess around with codes.

http://galexwongcsc148.blogspot.ca/
I picked this one because the posts were well-written. It represents honest impression of the course of the blogger and the blogger expressed feelings and opinions in a neatly manner.

I wish my blog also looks good to other students as well and I thank all the students for their effort cause it motivated me to keep going.

Until I become better, I will keep going and for now, I will prepare for the next week so I won't let myself down.

BST: Binary Search Tree

Binary Search Tree is based on the property that right child is bigger than the parent, and the left child is smaller. When binary tree is generated this is always true. Therefore, when search for an item, we can use this property and make searching process simpler instead of checking all the items in the tree.

The successor is the node that are next-largest. Because of the property of tree, we can conclude that there are three cases when look for an item.

1. If the node has a right child, then the successor is the smallest key in the right subtree.
2. If the node has no right child and is the left child of its parent, then the parent is the successor.
3. If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.

When deleting the node from the tree, we can use the case 1. Also, from the property of tree, we can conclude that the smallest number in the tree will be the left-most child. This is true because left child is always smaller than its parent. Then, again, the left child of left child will be smaller than the first left child, and so on. Thus, the left-most child is the smallest in the tree. Therefore, we can write a function that finds a minimum value in tree as follows:

def _find_min(node: BTNode) -> BTNode:
    '''Find and return minimal node, assume node is not None'''
    return _find_min(node.left) if node.left else node

This is a part of the code from the class BTNode and details omitted. Since finding maximum has been discussed in the class, I tried out finding a minimum based on the lecture. Notice that the only the left children are checked, and the process is recursive.

There are more things that can be done using Binary Search Tree. So, understanding this will be a crucial when it comes to data structures. 

The pain of recursion, and more

Recursion, recursion, and recursion!

Ok, so recursion is important concept. It seems I can't get away from this in this course. All the labs, assignment 2 was about recursion. And yes, the assignment! Minimax! Oh, you minimax! I still don't understand why I couldn't write this properly. I understood what is going on, and knew which part is recursive. But then, why is it so hard to make it work? I still can't figure it out what I am missing.

I see some students who are good at this and say that recursion is easy. Well, I have nothing to say. Recursion is not easy for me(, yet.) I wish I could naturally understand recursion like one of those guys, but I guess I have to take an honest, work-hard path to get to the level I want.

Generating Tree using nodes and children felt abstract. Sometimes, it is clear what I am doing but sometimes, depend on objects, it is quite hard to imagine how Tree is generated. For example, Minimax from assignment 2 was quite hard to bring the concepts into my head. Game state represents the state of current game and it is NoneType. Basically, Minimax uses this current game state to look all possible moves that can be chosen and suggest a strongest move based on this data. Of course, game state can be expressed as a string form, but I needed to use more to use Minimax.

I could tell where it's recursive but I couldn't write right recursive code. The assignment due is passed so there is nothing I can do any more, but I still kinda feel uncomfortable. Unsolved problems leave me such an uncomfortable, unpleasant feeling. Furthermore, despite of my frustration, the class goes on.

    def append(self, value):
        ''' (LinkedList, object) -> NoneType

        Insert a new node with value at back of lnk.

        >>> lnk = LinkedList()
        >>> lnk.append(5)
        >>> lnk.size
        1
        >>> print(lnk.front)
        5 ->|
        >>> lnk.append(6)
        >>> lnk.size
        2
        >>> print(lnk.front)
        5 -> 6 ->|
        '''
        new_node = LLNode(value)
        if self.front is None:
            self.front = self.back = new_node
        else:
            assert self.back, 'Unexpected None node'
            self.back.nxt = new_node
            self.back = new_node
        self.size += 1

So, this is a part of class LinkedList. At first, I was thinking about literally linked list, like multiple lists are somehow handcuffed each other kinda shape. It turned out I had a wrong concept. Just to help myself remember what this is... Linked list is created based on nodes. Suppose there are some nodes created with numbers like the docstring above. Initial LinkedList will be empty when it's called for the first time. Using append, I can append node into the LinkedList. Now, there is one node and the size of link is 1. If I insert another one, the new node will be at the back of the link, and the existing node becomes the front one. The size also changed to 2, the numbers of items in the link. Not only can I append items at the back of the link, I can also insert at the front, or check an item in the link. I found that drawing the pictures help me to figure out how each object becomes different attributes. 

I'm still little behind on all Tree stuff, so adding LinkedList on my study list is little burden now. But what can I do, I will keep working one step at a time. 

(Cheer me up, Fry!)

Visiting nodes in tree

So far, we've learned about binary node tree with nodes and children namely left child and right child. 

 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

Now, I know how to create Binary Tree Node. But what do I do with this? 

This tree also contains data so finding data that I want will be something I need to study. How do I find the data within the tree then? In order to find the specific data, I will have to go through each node in tree and verify if that is the correct one. Once I find the right one, I can return the result. 

There are three ways to visiting noes:

inorder
preorder
postorder

Inorder visit the left subtree inorder first, then node itself, the right subtree. Preorder, on the other hand, visit the node itself, then the left subtree preorder and the right subtree preorder. At last, postorder the left subtree postorder and the right subtree postorder and then visit the node itself. 

<Inorder>

<Preorder>

<Postorder>

Ok, it's not pretty drawings but there's so much I can do with mouse and I'm not really good at drawing. But pictures are way easier to understand and remember this for me, so, for the sake of my memory, I am taking the risk of public embarrassment on the web. At least, I will never forget this.