Sonata's SLOG!

Slog week 8 | Trees!

This week (and a bit last week) we focused on the tree ADT. I was excited to learn a new ADT but reluctant at the same time. Mainly because it takes me so long to get my head around a particular ADT. In order to fully apply one in exercises you literally have to change the way you think! This was even more complicated because of the fact that trees are a recursive ADT and use the concept of recursion extensively. I don’t have a full grasp on recursion yet (mainly due to lack of experience) and that it why trees seemed scary at first.

A tree is composed of many nodes. It is made up of parent nodes (aka roots), children nodes (leaves), or both! We call the arrows in between them edges.

A tree has many properties such as arity (or the branching factor) which determines how many children is the parent node allowed to have, depth which measures the amount of nested nodes in a tree, and height which is basically depth  + 1.

Prof Danny even said that a linked list is actually a specialized type of tree which actually now makes sense. It is always nice when two separate concepts reunite into one definition.

In this Slog, I shall be reflecting on my week 8 Slog (quoted above) about the tree Abstract Data Type or ADT. Trees in particular are an interesting topic to reflect on because my comprehension of them was completely changed when doing our puzzle assignment.

The puzzle assignment I just mentioned was a great practice for this subject because it shows how the use of trees is extremely versatile and highly efficient depending on the case or algorithm you implement it in. In this assignment, we had to search for a particular puzzle configuration (a solved puzzle configuration, basically). This task seems easy enough at first, but it is actually anything but easy. The search functions in this assignment is what made me fascinated with the tree ADT.  Our search had to start with an initial Puzzle node (a tree node that contains a puzzle configuration) and then that node refers to other extension nodes ( an extension is defined as a legal move). A diagram below is a good visualization of the situation

As we can notice, these aren’t ordinary tree nodes. They in fact contain two references one to the parent node, and another to the extension. This special type of tree is closely related to another ADT structure;  the linked list. This is why my view of trees ADT was changed. At this point, I realized that the ADT structure is actually not set in stone. And that as programmers, we are allowed to play with it and tailor it according to the needs of our program.For example,  with this structure I can implement an algorithm that searches hundreds (if not thousands)  of extensions and I can even tailor that algorithm to search the children first before moving on to the next level of children ( breadth-first search). This is all thanks to this structure which really resolves a lot of the logic problems that would go through implementing a search algorithm such as this.  

Overall, my impression of trees was changed because as I just mentioned, I realized that the overall form can be changed as long as you keep the references correct and so on. Also, trees are now a lot easier to think about and I seem to think they are a lot less “scary” than what I thought in week 8. This is of course due to lots of practice and hard work. I intend to keep practicing this concept because I’m genuinely curious as to what other applications I can apply this structure to.

This week we explored many topics and applications related to efficiency that are more theory based than what we’ve mostly done all semester. Efficiency is huge topic with so many branches and extensions and so it is kind of scary to look at it at first. The way we find efficiency in computer science is through meticulous calculations involving the code where you basically dissect each line and analyze what it does  whether it’s the best, worst, or average case. Thankfully this year we  will focus on worst case only without the average one since average case is a lot more difficult to calculate. Best case is basically useless. That’s because let’s say you’re selling this algorithm to some company; showing them performance on the best case isn’t very representative of the algorithm and it does not prepare clients for the worst. Therefore, worst case, for now, is a good measure of how fast and well-designed your algorithm is and so on.

Binary trees are a specialized type of tree with arity 2. They can be very useful when doing mathematical operations or even for searching! 

The init method for a binary tree is different. When it comes to children, a binary tree has only 2, so we classify them as left leaf and right leaf. This to me seemed comforting at first because we have less things to deal with, but when I started actually implementing code related to it I was very lost.

I got comfortable with iterating over a list when implementing functions that required recursion and when I did not have that choice anymore it became hard to change the way I think. I believe with more practice I shall be able to overcome this challenge.

This week (and a bit last week) we focused on the tree ADT. I was excited to learn a new ADT but reluctant at the same time. Mainly because it takes me so long to get my head around a particular ADT. In order to fully apply one in exercises you literally have to change the way you think! This was even more complicated because of the fact that trees are a recursive ADT and use the concept of recursion extensively. I don’t have a full grasp on recursion yet (mainly due to lack of experience) and that it why trees seemed scary at first.

A tree is composed of many nodes. It is made up of parent nodes (aka roots), children nodes (leaves), or both! We call the arrows in between them edges.

A tree has many properties such as arity (or the branching factor) which determines how many children is the parent node allowed to have, depth which measures the amount of nested nodes in a tree, and height which is basically depth  + 1.

The class started learning recursion this week ( and actually a little bit last week) where we defined what the concept is and had a simple example of its use. Recursion is a logical concept in which the function is defining something in terms of itself. A weird example that helped me understand it is Matryoshka dolls. each doll identical to the other is inside the other. This might be a limited example but it did help me have an initial idea of where the recursion concept was heading. 

Professor Heap introduced the nested list example, where we had to implement a function that calculated the depth of a certain nested list. Depth in a list represents how many nested lists there are in other lists. For example, [1, 2, 3] is a flat list or a list of depth 1. But [1, [2, 3]] is a list if depth 2. After understanding this, writing the API wasn’t particularly challenging and I thought implementing it wouldn’t be impossible but it would be tedious for sure. However, unsurprisingly, the professor used recursion to implement this method which was so efficient but at the same time I had a lot of trouble understanding it at a first glance. 

First, we had to think of an edge case where the object being used in the function isn’t necessarily an instance of a list and in which case our function (which counts nested lists) would return zero. From there, we also account for the case where we have an empty list [] and in that case even though the list doesn’t necessarily contain other elements it is still of type list and therefore it is of depth 1. Finally, we have to account for the most common case, a nested list. Once We get to that line, we are sure that object is a list of at least depth 1 and therefore before thinking about anything we should know that our result should add 1 to get a correct final result. The challenging part is to implement a function that somehow iterates over items in the object and counts if the items are lists, except we already have.

By implementing a list comprehension that iterates over the list using the function itself, we realize (mostly by tracing) that this method which returns the maximum of the output of the list comprehension + 1 works :

During this week, our group has officially handed in our assignment. We did it two days early too which I consider an  achievement. This was mostly due to good group dynamics; meaning every member was dedicated to scheduled meetups and we all gave it our best and contributed. The assignment ran perfectly ( or so I believe, we didn’t get the marks back yet) and we were thrilled to have finally finished it. 

The logic behind the assignment did not seem so tricky at a first glance but once we got to implementing our simulation module, our initial understanding of the assignment was completely transformed. We did not take in account cases such as for example when a rider cancels a ride the driver should not schedule a pickup event (and in our faulty code it did anyway). 

to find these bugs we used the debugger, which is something I haven't tried before due to it being “optional” in CSC108 but one of my group partners taught me and I found it extremely useful and efficient compared to the alternative which was to stare at those 7 or 6 modules repeatedly hoping to catch an error somewhere.

It was also helpful to print out the output. Especially in the simulation method because it was important to see what interpretation the machine was reading as opposed to the way it is actually supposed to be implemented.

linked list ADT is definitely an unfamiliar data structure because of the way the elements are structured. Coming from the -perhaps too convenient- list built-in type in python, I couldn’t wrap my head around the uses of a linked list. I simply did not see the point. 

One difficult concept that I understood is that each node in a linked list is composed of two attributes, not only the value, but also the reference. This is clear when implementing the init parameters of LinkedListNode( a subclass of LinkedList)

The highlighted parameters here value and next_ represent the contents of one node of the linked list and a reference to the next node respectively.

Additionally, when implementing methods related to linked list it was immensely helpful to draw pictures and understand as well as keep track of how element’s values and reference operate under the method 

An example of this is implementing the append method during an exercise in class, it was important to keep track of all the moving pieces and a drawing in this case was the best thinking strategy as shown below

As is known, a linked list has 3 attributes; front(node), back(node), and size. when appending we are changing the last node’s reference to point to the new element we’re appending rather than having no reference at all. 

When drawing this picture, it helps us form the strategy we should go about tackling this problem, makes us understand the data structure even better, and reminds us about smaller details that we might forget such as changing the size (since an element was appended making the list size increase).

Also, during the implementation of this method, I made thinking of corner cases a habit because a lot can go wrong when we do not account for the case where  a linked list and therefore we should account for these cases accordingly. 

our append method is therefore:

CSC148 teaches many important ADTs or abstract data types such as queues and stacks i. 

Queues are of type LIFO which means “Last In First Out” and Stacks are of type FIFO or “First In First Out”. These abbreviations simply explain the order in which items are added or removed to these data type lists. 

A good analogy to remember how these ADTs work is to picture Stack as a stack of chairs, you can only remove the last chair you put on top of the stack. 

Similarly, I tend to think of the Queue’s elements as people standing in line for a coffee, the first person or item that lined up, leaves first. 

for these ADTs we use the built in list class to build them as follows 

from there we can write functions to arrange how items are inserted to or removed from  this data type using methods such as add, remove, or is_empty (a method that checks if the list is empty) 

Also, here we see how we can protect some methods from client use by adding an underscore in self._contents which should warn the user (according to python etiquette apparently) that they should not mess with this specific method 

To understand this better, I read an important chapter in course notes that discusses that same topic and I find that using the property function which redirects and restricts (to some degree)  client access is a lot better

We have discussed this method briefly in class when implementing rational.py where we forced num to be an int by only using the property method as shown below:

Going back to Stacks and Queues, their implementation is actually is not that challenging once we fully comprehend their structure and know how to use the built in list method in Python to our advantage; such as appending in a list which we can rely on when adding an element or method pop which we can also use when removing an element