Week 9

This week we studied about linked list. It is a fun topic that is not too hard but definitely not too easy.

Conceptually speaking, linked list is not hard. Every node has a value and a link to the lists ahead of it. The first list is called the front and the last list is called the back. Many operations can be performed with linked list. The most common one is to either add a node to the front or to the back of the list. While adding a node to the front is easy, adding it to the back is relatively more complicated. This is because when we add a node to the back, we not only have to link our back with the new node, but we also have to link the node before our previous back with our previous back. This creates some complexity, and often a while loop is used to solve the problem.

The thing I find with linked list is that the concept is fairly easy, and yet it is extremely prone to mistakes. You can miss the question by simply forgetting to link two nodes together. This nature of linked list should alert us when we solve a linked list question. We must be super careful with our logic and never forget what links with what.

Week 8

This week we studied binary trees. This topic is rather interesting because the outcome of the tree is very predictable, which makes it easier to computer compared to regular tree. Each binary tree will have two children, and the child to the left will always have the value less than the value of the node, and the child to the right will always have value greater than the node. This feature of binary tree allows us to perform operations on the tree with much ease. For instance, I can easily search for a value in the tree by comparing the value with the value of the node. If it’s less than the node and it exists, I will know that it must be contained in the left tree, else it must be in the right. Using this feature, I can easily find my intended value. In addition to the easiness of performing operation on trees, operations can also be performed with high efficiency. This is because instead of working with the whole tree, the nature of binary tree often allows us to only operate with half a tree. This is significant amount of time saved, and will likely allow the program to run more smoothly and quickly.

We also studied about tree traversal this week. To be honest I do not necessarily get what is the point behind the different way of visiting a tree. My opinion is that it’s most efficient if we just stick with one method. Well I am just a noob in the industry so what can I say haha J

To conclude, this week’s work has been rather fun and interesting. I am however a little bit upset that our TAs went on strike and we no longer have tutorials. This is bad for me as I always learn a lot from the tutorials.

Recursion

Recursion is a useful tool that we learned in CSC148 which was helpful for us to solve many complex and combinatorial problem. For instance, using a simple recursive method sum_list, we were able to solve the rather complicated problems of lists within lists.

In CSC148,we were also taught about trees, which is just an application of recursion. Trees are potentially recursive because when we solve a problem related to trees, we always try to reduce it to the root, which is potentially the base case. The tree is a perfect demonstration of the fundamental feature of recursive function .In my opinion, recursive functions have two attributes. A base case in which the recursion stops and a line of code that will operate recursively and eventually reduce the input into meeting the condition of the base case.

The most difficult part with writing recursive function actually lies on identifying the base case. This can be hard sometimes as the base case may not be that obvious. However, once we have the base case established, all we have to do is to write a recursive function that returns the input into fulfilling the condition of the base case, and we are done.