Week 8 - Linked structures in Week 7

In week 7, the professor covered the concept of linked lists. A linked list is a recursive data structure that is made up of connecting nodes. Each node contains a reference to the next node in the list. As usual, when I was first introduced to this concept in class, I found it quite confusing and hard to understand. But after reading over it again and visualizing it in my mind and on paper, I was able to make sense of how it worked. Asking the professor also helped. 

To teach this concept, the professor created a class called BTNode, which had 3 attributes: data, left, and right. Data is the root node, and left and right represent the children of data. He then showed us some methods that used these attributes along with some additional ones to create representations of this class. Again, this was confusing for me at first, as the code seemed complicated and odd to be able to create some form of a visual representation of the nodes in the class. An example of this is the __str__ method. It involved indenting in order to distinguish the children and space them out. I wonder how people can figure out how to code this, as it seems so complicated for me to code. I can visualize it and draw it on paper easily, but when I have to translate it into code, it seems like a burden.

The professor also showed us how arithmetic expression trees are represented. The values in nodes don't necessarily have to be numbers. They can even be operators, such as the ones in the tree below(a representation):

       7.0

+           4.0  

       *

             3.0

The professor also showed us how to evaluate a binary expression tree, using the eval() function. I found this particularly interesting and useful as it simplifies the job of evaluation by combining the values in the nodes into one single string expression and evaluating that expression. 

Furthermore, we were shown how to evaluate a binary search tree inorder, preorder and postorder. Additionally, our professor showed us added ordering conditions to a binary tree, and were taught how to check if a value was in a tree by calling a recursive function on the tree. Overall, I found this lecture interesting, but I do find the course becoming progressively more challenging. However, I try to curb this challenge by reading over concepts again and again and practicing them, and aim to continue to seek help when necessary.

Week 7 - Recursion

For me, tracing recursion is not really a difficult concept, as it involves going into a list and just using a function on the various elements in the list. It basically involves a function calling itself, as mentioned previously. An example of recursion on a list can be:

L = [[1, 5], [9, 8], [1, 2, 3, 4]]

sum([sum_list(x) for x in L]) - this takes the sum of elements at each index position in L, or just x if x is an integer

To trace this, just do:

>>> sum_list[[1, 5], [9, 8], [1, 2, 3, 4]]

>>> sum([sum_list[1, 5], sum_list[9, 8], sum_list[1, 2, 3, 4]])

>>> sum([6, 17, 10])

33

Tracing inside lists more complicated than this one can be confusing, but if one just traces simpler examples first, he/she can automatically write the result of the nested list in upcoming examples of lists of increasing complexity. They will not need to trace through individual elements in the nested lists again, such as [sum_list(9), sum_list(8)]. In fact, when one moves on to tracing more and more complicated list calls, they must not do this. This is because they would have already traced through like this in previous simpler examples.

The depth of the list is also not that difficult to understand. It took me some time, however, to understand how the code for determining the maximum depth of a list made sense and worked. This is the code for determining the depth for the list:

if instance(L, list):

     return 1 + max([depth(x) for x in L])

else:   # L is not a list

     return 0

At first, I was confused as to how this function was able to determine the depth of a nested list with just the word depth(x) in its code. Before finding out the solution, I thought about it to myself and got the correct answer just by seeing the number of lists and nested lists. A simple example of this is:

>>> depth(17)

0

>>> depth([1, 2, 3])

1                   # because there is only one list

>>> depth([3, 4, [2, 5], 9])

2                   # because there is a list and nested list

Later, I figured out how the code worked, just by remembering that it was nothing but recursion at action! Since it called itself, depth(x) works on a nested list, such as [2, 5], just like it would work on a list without a nested list, such as [1, 2, 3]. 

Furthermore, the professor also covered how to find the maximum number in a simple list, lists that are one deep, two deep and etc. For example, this is a call to a simple/flat list:

>>> rec_max([2, 5, 1, 3])

>>> max([rec_max(2), rec_max(5), rec_max(1), rec_max(3)])

>>> max(2, 5, 1, 3)

5

When the list increases in complexity, it must be evaluated in the same way as the sum_list() and depth() functions. One thing that I found particularly fascinating was recursion in a file named tree_burst.py. This gave a visual application of recursion and I found this particularly interesting, as it involved red, blue and green arrows branching out in 3 different directions. These arrows formed a ternary tree. I didn't fully understand how this implementation of recursion worked, but I enjoyed it as I like learning through visuals.

By far, this course continues to become more and more interesting, and challenging as well. I look forward to upcoming material and am a bit apprehensive of their level of difficulty.