Week 8, 9, 10

Main topics:

LinkedLists(W8):
    LinkedList is a brand new topic for me. It is a data structure. Every linked list has an item and a link. The link can either be none or a new linked list. In order to modify the linked list, (by modifying, I mean to add or delete items to the linked list), I need to first find the right place, and then modify the whole list by changing self.item and self.link simultaneously.
    The most difficult part is the first step. I need to think through the whole process and find the right spot for changing. The thinking process is very time consuming. If I am clear of the process, coding is not that difficult.

Binary Search Tree(W9):
    Binary Search Tree is an extension of LinkedList. The rough idea of that is: every BST has a item and two children(either or both of them can be none). If not None, the left children are less than the item and the right children are bigger than the item.
    In order to modify the BSTree, (by modifying, I mean insert a value to its right place or delete the value), I need to do the exact thing as I do in Linked List. I need to first find the right place to modify. The more challenging thing is when I need to delete an item, I also need to consider restructure the tree a little bit. When a inner node is deleted, I need to find the biggest item in the left tree to be this new inner node and connect the other nodes properly.
    When we want to search some value in the binary search tree, it will save us a lot of time. Because for each recursion step, we only need to consider half of the tree. So Binary Search Tree does an amazing job in reducing the searching time.

Some Sorting Methods(W10):
    Reviewed some sorting method learned in CSC108 including insertion sort and selection sort. The idea of Big O is new to me. Insertion sort and selection sort are both quadratic methods. When the size of data is small, it performs well. However with the increase of the data size, the time it spends will increase quadratically. Thus when the size is big, it doesn't perform very well.

Assignment & Exercise:
Assignment 2I (W8):
    Assignment 2I is to design a class. The key part is to create subtrees and supertrees to avoid repeated calculations.
Exercise 3 (W9):
    1-We are asked to produce a tree if its preorder and inorder is given. The fun part of it is to properly using recursions.
    2-We are asked to return the sum of the keys from the root to the deepest leaf in t.
Assignment 2I (W10)
    Assignment 2II:
    Assignment 2II is harder than what I have thought. In fact, every function needs intellectual work. I need to first write down the base cases and then think about the recursion process. Prof Danny's explanation was really helpful. After knowing the rough idea of the method and the base cases, writing recursive code is easy. PS, we spend more time on 'debug' than write code in the begging. It took us 2 days to fix bugs.