Looking back at all my posts so far, I have to agree with everything that I wrote except for the post about Why Geeks Need to Know How to Write. The reason being is that, for course materials, I mainly focused on writing about my understanding of the concept and relaying it in terms that someone who may not understand the concept would start to understand.
However, in my Why Geeks Write post, it was mostly my opinions. Now that I have written many slog posts, I can say that geeks need to know how to write because we need to be able to explain complex concepts to those who may not understand them. Take all my other slog posts for example, if someone who didn't know computer science happened to find my blog and started to read it, there is at least a small chance that they will come out having a general idea on what I'm talking about because I have included easy to understand concepts such as diagrams, code, examples, and explanations on why they work or why we need them.
This can also be brought into coding as well. Code without documentation will be useless to others because they will not know what the code does, and they will not want to touch the code either in fear of breaking it. Documentation is essential to a working program because it allows others to understand how to use the code.
I also took a look at my other classmate's slogs and so far we have talked about the same concepts and experiences from course material to assignments and tests. One slog, keirnslog.blogspot.ca/ actually put his lab solutions in his posts which I thought was really interesting because it allows me to see how he implements his code. It gives me a totally different view on how some functions could be done which is really helpful. Also for his post about why geeks write, is very similar to my reason above. Keirn's main point is that we write to clarify things for others.
That's all for this week, thanks for reading.
Tuesday, 31 March 2015
CSC148 Post #8
Not much happened this week other than writing test 2. I found that the test was pretty fair in terms of difficulty. It tested us on binary trees and linked lists and the recursive functions that go into these ADTs. The lab was quite short too as it was about the insert and delete functions in a binary tree. Essentially what they do is insert values into the tree and also delete values from a tree.
The thing that I did not understand at first though was that when we delete a value, what happens to that slot? Does it stay empty? So what really happens is that when a value is deleted, the next child node of that value replaces it.
Anyways, since there was no lab this week because of the strike, there hasn't really been much going on in lectures. Unfortunately I have nothing else to write about for this week, but thanks for reading!
Thursday, 12 March 2015
CSC148 Linked Lists Post #7
During week 8, we took a look at another ADT called Linked Lists. A Linked List is sort of a linear set of nodes where each node can only have one child node. An easy way that I thought of to help understand what Linked Lists are is to think of a Tree with only one child node for each node.
Now for Linked Lists I found that this concept was actually easier to understand compared to Binary Trees, and Binary Trees are already pretty easy to understand. I think it's because there is only one branch direction now, instead of a left and a right.
Another thing that I noticed about Linked Lists is that there is barely any recursion involved. In our labs, I used recursion only once in one function, but that was only to bring the arguments up from negative to positive to satisfy our if statements.
So what exactly is a Linked List?
A Linked List has three things, a front, a back, and a size. The front refers to the first node of the Linked List, the back refers to the last node of the list, and the size is the total number of nodes in the Linked List. These nodes, in our Python implementation are called LLNode, where each node has a value and a "child" node called nxt (since "next" is a built-in function). If you look at the representation of a Linked List, you can see it sort of resembles the representation of a Tree.
For example:
LLNode(1, LLNode(2, LLNode(3, LLNode(4))))
In this example, the front of the Linked List would be LLNode(1), the back would be LLNode(4), and the size would be 4. If you take a close look, you can notice that it is sort of like a Tree where each node has a child node, except for LLNode(4), which would essentially be a leaf. The only difference is that Trees can have multiple children coming from the same parent node, where as in Linked Lists, there can only be one.
Taking that into consideration, we can see that Linked List could be used in Trees to help represent them. A path in a Tree could basically be a Linked List because the path is referring to a linear set of nodes. For example,
I coloured each path of this Tree to show how a Linked List representation would work. Since in each path, there is only at most one child node coming from the previous node, We can use Linked Lists to represent each path. For example the red path would be, LLNode(A, LLNode(B, LLNode(D))), and the blue path would be, LLNode(A, LLNode(B, LLNode(F))).
That's all I've got this week about Linked Lists, thanks for reading.
Now for Linked Lists I found that this concept was actually easier to understand compared to Binary Trees, and Binary Trees are already pretty easy to understand. I think it's because there is only one branch direction now, instead of a left and a right.
Another thing that I noticed about Linked Lists is that there is barely any recursion involved. In our labs, I used recursion only once in one function, but that was only to bring the arguments up from negative to positive to satisfy our if statements.
So what exactly is a Linked List?
A Linked List has three things, a front, a back, and a size. The front refers to the first node of the Linked List, the back refers to the last node of the list, and the size is the total number of nodes in the Linked List. These nodes, in our Python implementation are called LLNode, where each node has a value and a "child" node called nxt (since "next" is a built-in function). If you look at the representation of a Linked List, you can see it sort of resembles the representation of a Tree.
For example:
LLNode(1, LLNode(2, LLNode(3, LLNode(4))))
In this example, the front of the Linked List would be LLNode(1), the back would be LLNode(4), and the size would be 4. If you take a close look, you can notice that it is sort of like a Tree where each node has a child node, except for LLNode(4), which would essentially be a leaf. The only difference is that Trees can have multiple children coming from the same parent node, where as in Linked Lists, there can only be one.
Taking that into consideration, we can see that Linked List could be used in Trees to help represent them. A path in a Tree could basically be a Linked List because the path is referring to a linear set of nodes. For example,
That's all I've got this week about Linked Lists, thanks for reading.
Thursday, 5 March 2015
CSC148 Binary Trees Post #6
After learning about Trees, we have moved into learning about Binary Trees. Really the only difference is that Binary Trees only have at most two children branching off the parent node. I found that for this topic, it was easier to understand than regular Trees because there were less children involved. I also found that the recursive code for Binary Trees to be a bit easier as well.
In class, we got two worksheets on Binary Trees. The first one talked about taking a look at the Binary Tree and evaluating the content of the Tree by first checking if the left and right nodes are empty and then recursively evaluating the left and right nodes.
The idea is that since we have only two children nodes, it is easy to represent a python expression with it, for example, the parent node could be an operator like "+" or "*", and the children nodes could be values such as 3.0 and 4.0. The recursive function would check if the children nodes are leafs, if not they will evaluate them using the parent node as the operator.
The second worksheet that we got goes into a bit more depth of what we can do with Binary Trees. Lets say that we have a Binary Tree with a ton of children nodes branching off and the root node contains some value. The problem is that we want to find a value that is somewhere in the Tree, but it would be inefficient to check every single node within the Tree.
How could we avoid that? Well Binary Trees have a special property where the values in the left side of the Tree will always be less than the value of the root node, and the right side of the Tree will be greater than the root node. If our root node value is 50, and the value we are looking for is 18, then we can immediately disregard the right side of the Tree and only look at the left side since everything on the right side will be greater than 50. This way we can save a lot of time and effort of having to check every single node in the Tree.
What is so great about this property is that when you implement it into a recursive function, we can continue to disregard the sides of the children nodes to even eliminate more checking required. From the previous example, lets say the value of the next child node from 50 on the left is 30. Since 18 is less than 30, we can disregard everything that is on the right side of 30 and focus on the left side, and we can do this again and again until we reach 18.
So Binary Trees are very friendly when it comes to searching for stuff in them, but I have yet to see a more practical use for them. Though compared to regular Trees, I think the difference is just in running time and which is more efficient. I also think that Binary Trees are rather job specific as well and that they are mainly used for their binary search properties. That is all for this week about Binary Trees, thanks for reading!
In class, we got two worksheets on Binary Trees. The first one talked about taking a look at the Binary Tree and evaluating the content of the Tree by first checking if the left and right nodes are empty and then recursively evaluating the left and right nodes.
The idea is that since we have only two children nodes, it is easy to represent a python expression with it, for example, the parent node could be an operator like "+" or "*", and the children nodes could be values such as 3.0 and 4.0. The recursive function would check if the children nodes are leafs, if not they will evaluate them using the parent node as the operator.
The second worksheet that we got goes into a bit more depth of what we can do with Binary Trees. Lets say that we have a Binary Tree with a ton of children nodes branching off and the root node contains some value. The problem is that we want to find a value that is somewhere in the Tree, but it would be inefficient to check every single node within the Tree.
How could we avoid that? Well Binary Trees have a special property where the values in the left side of the Tree will always be less than the value of the root node, and the right side of the Tree will be greater than the root node. If our root node value is 50, and the value we are looking for is 18, then we can immediately disregard the right side of the Tree and only look at the left side since everything on the right side will be greater than 50. This way we can save a lot of time and effort of having to check every single node in the Tree.
What is so great about this property is that when you implement it into a recursive function, we can continue to disregard the sides of the children nodes to even eliminate more checking required. From the previous example, lets say the value of the next child node from 50 on the left is 30. Since 18 is less than 30, we can disregard everything that is on the right side of 30 and focus on the left side, and we can do this again and again until we reach 18.
So Binary Trees are very friendly when it comes to searching for stuff in them, but I have yet to see a more practical use for them. Though compared to regular Trees, I think the difference is just in running time and which is more efficient. I also think that Binary Trees are rather job specific as well and that they are mainly used for their binary search properties. That is all for this week about Binary Trees, thanks for reading!
Subscribe to:
Posts (Atom)