This week was mainly focused on A2 and the working of regexs. This week was mainly focused on A2b as A2a was done immediately upon return from reading week. A2b focused more on the actual running of code whereas A2a served as a template for the rules of the various trees such as bartree and startree.
My group and I encountered problems straight away when starting the assignment. We wondered just how exactly we were going to go about writing these functions. The first one was is_regex that determined whether we were working with a regex or an invalid one. We initially hard-coded the entire function which took around 200 lines. This was very inefficient and had some problems while running. We later discovered that this can we written recursively and can be done in less than 50 lines of code without errors occurring. We then began thinking and approaching the problems in a more recursive manner and tried to incorporate recursion in all of the functions. Permutations of the regex was quite hard to do but we were eventually able to do it with recursion.
Wednesday, 26 March 2014
Week 8 - Linked lists
This week we were introduced to the concept of linked lists. Linked lists are kind of similar to trees as they have a value while referencing another list. Trees hold a value and reference its "children" thus making these two things similar. Linked lists are important data structures that can be very important in many fields of computer science.
What we have explored in linked lists is the fact that each linked list holds a node called a cargo. This cargo is a value that is stored. The other part of the linked list is the reference to another linked list node. This other node will also hold a cargo as well as another reference until eventually the linked list references None which marks the end of the linked list. As one might predict, this type of referencing and cargo holding can be done recursively. Since the linked list can reference upon itself, recursion makes the traversal of this linked list very simple to do. Another thing to note about linked lists is that they cannot be indexed and must be iterated over in order to go through the list. This is another reason why recursion is such a good method to go about handling linked lists since recursion will iterate until you set a condition that the function must meet. Linked lists is thus interesting and very fun to learn about.
What we have explored in linked lists is the fact that each linked list holds a node called a cargo. This cargo is a value that is stored. The other part of the linked list is the reference to another linked list node. This other node will also hold a cargo as well as another reference until eventually the linked list references None which marks the end of the linked list. As one might predict, this type of referencing and cargo holding can be done recursively. Since the linked list can reference upon itself, recursion makes the traversal of this linked list very simple to do. Another thing to note about linked lists is that they cannot be indexed and must be iterated over in order to go through the list. This is another reason why recursion is such a good method to go about handling linked lists since recursion will iterate until you set a condition that the function must meet. Linked lists is thus interesting and very fun to learn about.
Week 7 - More Recursion!
Week 7 began with more recursion and more function writing in recursion. This time, recursion was done alongside trees. Traversing a tree can be very tiresome if the tree is very big especially when we do not know the exact size of it. This is when recursion comes in and allows us to traverse the tree without having to know how big or small it is.
We applied this idea to trees in this week's CSC148 course. An example of this is comparing the root of a tree to its children. We recursively call the function with every recursive call checking to see whether the root is greater or less than the left or right subtree. With a given condition, the recursive call will stop once we have reached a subtree that is less than that of the root. This is very easy to do with recursion as the function will keep going until the condition is met to stop recursing. When doing recursion like mentioned before, we must keep in mind of a condition to stop the recursion or else the computer will run out of memory and the maximum recursive depth is reached. This condition is usually one that is not met immediately and only reached after going through the tree (answer found in one of the children of the root). This method allows us to not care about the size of the tree as the recursion will do that for us. If we didn't do recursion, it might become extremely difficult to program as the tree is not defined as a finite number.
Recursion is extremely helpful in many situations not just in trees. We however explored trees this week and the traverse of it became much much easier with recursion. Without recursion, tree traversal will be very annoying and hard to do!
We applied this idea to trees in this week's CSC148 course. An example of this is comparing the root of a tree to its children. We recursively call the function with every recursive call checking to see whether the root is greater or less than the left or right subtree. With a given condition, the recursive call will stop once we have reached a subtree that is less than that of the root. This is very easy to do with recursion as the function will keep going until the condition is met to stop recursing. When doing recursion like mentioned before, we must keep in mind of a condition to stop the recursion or else the computer will run out of memory and the maximum recursive depth is reached. This condition is usually one that is not met immediately and only reached after going through the tree (answer found in one of the children of the root). This method allows us to not care about the size of the tree as the recursion will do that for us. If we didn't do recursion, it might become extremely difficult to program as the tree is not defined as a finite number.
Recursion is extremely helpful in many situations not just in trees. We however explored trees this week and the traverse of it became much much easier with recursion. Without recursion, tree traversal will be very annoying and hard to do!
Sunday, 2 March 2014
Week 6 - Trees
Week 6 began with the talk about the concept of Trees in computer science. Essentially, Trees are a type of data structure that is used in computer science that is a way to store information. The trees that we did were binary trees starting out with the root with each root having children or leaves called nodes. Each node can have a value and the tree can be traversed recursively. Trees are a very convenient way to store information since the leaves of a binary tree can be treated as two different keys with values. The keys can be ordered so that the side of a tree can be keys with values that are smaller than another side. Thus, traversing a tree becomes very efficient since you can code it recursively to always go towards the smaller side of a tree in order to find the smallest or largest value. Due to the way a binary tree is implemented, you can search for values in the nodes recursively since you know which of the two leaves of a node has a certain property and recursing for long enough will get you the value that you are looking for. Trees can be thought of as a more complex list to store information in.
Like most things in python, trees can be written in a object oriented way. The first step is to initialize your tree by setting up the different nodes and seeing whether you want a binary tree or another type of tree. The rest of the functions can be anything that you want such as the length of your tree. In most cases, the traversing of your tree is done recursively. In the binary tree, each node contains 2 possible keys and you recursively decide which key to take depending on what you want. Eventually the recursion will take you to the value you need within the tree data structure.
Like most things in python, trees can be written in a object oriented way. The first step is to initialize your tree by setting up the different nodes and seeing whether you want a binary tree or another type of tree. The rest of the functions can be anything that you want such as the length of your tree. In most cases, the traversing of your tree is done recursively. In the binary tree, each node contains 2 possible keys and you recursively decide which key to take depending on what you want. Eventually the recursion will take you to the value you need within the tree data structure.
Subscribe to:
Posts (Atom)