Binary Tree, Sorting, and Big-Oh (Week 9- 10)

Since we learnt about tree object, the recursive feature of it made me increasingly curious about what else we could develop from this object. During Week 9 we mainly learnt about the Binary Tree Node and how to construct a Binary Search Tree(BST). A Binary Search Tree is basically a recursive node-based binary tree object with three special features: First, the left subtree of a node contains only nodes with keys less than the node's key; second, the right subtree of a node contains only nodes with keys bigger than the node's key; and third, there is no duplicate nodes.

There're several very representing methods of a BST, including insert, find, delete, and height. Learning about how to write those methods in class really inspired me a lot. Basically we need to right a helper function for almost all of those methods, which is quite challenging but helpful to me because I haven't had many chances practicing writing helper functions. Since all the functions and method are recursive, I achieved a more thorough understanding of recursive functions.

What's more, Week 9's lab is also both very challenging and inspiring. Together with my partner, we drew many pictures of what the function is going to do before starting to write the code. TA also helped us a lot on understanding the purpose of each function and how we could avoid unnecessary extra work.

During this week which is Week 10, I feel excited about learning about two more sorting method other than the three basic ones I learnt in last semester's 108 course. They are very efficient compared to the ones we have learnt and also make a lot of sense to me because I have had a decent understanding of recursive functions.

The first one is called Quick Sort which sounds good :) Basically it picks the very first value as a pivot value from a list of values and split the whole list in to three parts- the left half which contains values smaller than the pivot value, the pivot value, and the right half which contains values greater than the pivot value. After doing this step recursively, we can finally get the result which is a sorted list. However, this can be very time-consuming if the list given is already sorted. After quite an amount of discussion, we come up with an idea that we should randomly pick the pivot value instead of using the first value of the list as a pivot value. In this way the possibility of accidentally picking the smallest value as our pivot value decreased to a large extend.

The second sorting method I learnt is Merge sort which behaves even better than Quick sort. Briefly speaking, it divides the whole list into approximately equally half and compare the two smallest values from both sublists and send the smaller one to the merge list. By doing this recursively, we can get the resulting sorted list very fast.

By doing lab 10 this last week, I can see more directly from the graph me and my partner made out of each sorting algrithm. Appearantly the built-in sort method does the best job among all. The three sort methods we learnt from cs108 course has a running time of about n^2 while the other three methods we encountered this semester only require log(n) with base 2.

Looking forward to next week's class and hoping I can do well on the second test!  

CSC148 SLOG - Recursive object Tree and LinkedList (week 6- 7)

Recursive objects are amazing. The key thing to understand when writing recursive function is figuring out what the base case is. After figuring out what basically we want the function to do, the rest part is to repeatedly call the function itself until reach the base case.

Just like the turtle we learnt about last week during lecture, the very representative object called Tree during week 6's lecture inspired me a lot. I discovered that the intellectual merit of recursive functions is that it allows us to write the code in a optimized and efficient way when encountering difficult situations.

What's more, the most fascinating thing about recursive functions is tracing through them. For instance, by learning about the three traversals of a Tree object- preorder, inorder, and postorder, I saw that tracing through recursive functions can be sort of tedious, however, eventually I can reach the base case and solve for the correct answer.

Similarly, the lectures on LinkedList object during week 7 are also very informative. Conceptually, there's a sequence of nodes within a linked list, each with a head and a reference to the rest, which is also a linked list. As shown below, a linked list is basically a nested list with references.

When initializing the object, we used the default value None for both the head and rest. And surprisingly, prepending a new head to a linked list is not that simple as I thought, there're three procedures:
    1. Start the rest of the list with the current attributes by shallow copying        them
    2. Change the current head to the one passed in
    3. Change the current rest to the copy.

Writing the __contains__ builtin function also helps me understand the structure of a LinkedList object.