JA5. Non Binary Trees¶

Statement¶

The Learning Journal is a tool for self-reflection on the learning process. In addition to completing directed tasks, you should use the Learning Journal to document your activities, record problems you may have encountered and to draft answers for Discussion Forums and Assignments.

Your learning journal entry must be a reflective statement that considers the following questions¶

1. Describe what you did. This does not mean that you copy and paste from what you have posted or the assignments you have prepared. You need to describe what you did and how you did it¶

This was the 5^th week of this course, it was all about the Non-binary trees.
I started by reading the chapter 6 (Shaffer, 2011) of the book, it was a light reading compared to the previous week which I did not finish the last week.
I then, read what’s left from the previous week, and I was able to understand it better.
I also watched around 3 - 4 hours of youtube videos about the topic, and it was very helpful.
I then, worked on the discussion assignment, which was about binary trees.
I did the graded quiz and reviewed the assignment of the last week (week 4).

2. Describe your reactions to what you did¶

The reading were lighter in size, but it was a bit harder to understand.
The binary trees were defined in a concrete manner, but the flexibility of general trees to host any number of children, made it harder to understand and implement.
I would say that the general trees helped in sharpening my understanding of the binary trees, and I’m confident that the coming weeks will help me understand the general trees better.

3. Describe any feedback you received or any specific interactions you had. Discuss how they were helpful¶

The discussion assignment asked about conducting asymptotic analysis for the time complexity of the binary tree operations, and I was able to do it correctly.
The assignment asked about discoursing the Omega, Big-O, and Theta notations, and this triggered a back and forth discussion with my colleagues, and it was very helpful.
This week I also received a disappointing feedback from my colleagues on the unit 4 written assignment, due to my code not referencing Jeliot, although I attached the output of the code within the assignment.

4. Describe your feelings and attitudes¶

I’m surprized that most students ignored the Omega, and Theta notations in their assignments and only discussed the Big-O notation.
It is still tricky to define and use these three notations, but I’m trying myy best reading every possible assignment that I feel interesting.

5. Describe what you learned¶

I learned about non binary trees and their various implementations, these implementations are:
- Parent Pointer: Nodes hold pointers to their parents.
- List of children: Nodes hold pointers to their parent, and a linked list of their children.
- Left Child, Right Sibling: Nodes hold pointers to their parent, leftmost child and the first right sibling.
- Dynamic Nodes: Nodes can hold their dynamic number of children either in an array or a linked list.
- Dynamic Left-Child/Right-Sibling: Nodes hold pointers to their parent, and are a root in a binary tree that holds their leftmost child and the first right sibling.

6. What surprised me or caused me to wonder?¶

The use of sequential Tree Traversal to implement the general trees, it was a very interesting approach that saves a lot of memory and time.
It was a clever way to serialize/deserialize trees while saving them to disk or loading them from disk, or even sending them over the network.

7. What happened that felt particularly challenging? Why was it challenging to me?¶

The implementation of find/union was a bit challenging, I understood the rules of Weighted union and path compression, but I still couldn’t understand when and why to use them, and why don’t we just keep the trees separate.

8. What skills and knowledge do I recognize that I am gaining?¶

I gained a better understanding of the binary trees, and general trees and their implementations.
I understood the effect of extra pointer in a node (e.g. parent pointer, leftmost child pointer, etc.) and how they affect the time and space complexity of the tree operations.

9. What am I realizing about myself as a learner?¶

I’m realizing a pattern in my learning process, that I fully understood this weeks learning in the coming weeks as the latter chapters build on the previous ones and continuously referencing knowledge gained in previous chapters.

10. In what ways am I able to apply the ideas and concepts gained to my own experience?¶

Understanding the file system as a tree, and how the file system traverses the tree to find the files and folders.
Understanding the concept of O(log n) in a practical manner and automatically thinking of time complexity when I’m writing code if I expect large number of elements.

11. Finally, describe one important thing that you are thinking about in relation to the activity¶

I finally succeeded in starting the Jeliot on my machine, it is not the latest version but an older one, but it is working, and I should be able to use it in the coming assignments correctly.

References¶

Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 6.
Barnett, G. & Del Tongo, L. (2008). Data Structures and Algorithms: An Annotated Reference with Examples.