This week I've decided to talk about trees, as they seem to be the focus of the course at this time. As Professor Heap outlined, the name 'tree', while also corresponding intuitively to the species of plant, appears to come from graph theory.
As I'm sure the reader knows, the tree is a recursive data structure, defined in terms of its nodes, which in a tree contain both a value(say an integer) and some number of references(potentially zero) called children(which is a bit of mixed metaphor, next to all the plant stuff). A tree is a root node and its sub-trees(which each have a root node), and so on and so forth. At the bottom of a tree is a "leaf" which sensibly is a node which does not connect to anything(this is if a tree is finite; but practically I don't think we will ever have to deal with infinite trees except as an error).
By this definition a linked list is simply a tree with a root node and a single branch between each of its nodes. In fact a node is also a kind of tree, a root with no sub-nodes.
So far we've stuck mainly which with binary trees, which are, unsurprisingly, trees where each sub-node has two children(which may be other nodes or None). Binary trees obviously present some advantages: it's easier to write code to traverse them, for one, as one knows in advance that each node has two children(and therefore at most two subtrees). These are actually part of the focus of assignment two(which I need to get working on!).
Most of my interest in trees comes from their structure. It's very elegant, an elegance that comes from its recursive structure and implementation. What I'm not so sure about at this point is their utility. The only real 'use' for trees we've seen so far is their ability represent regular expressions in assignment two, but I'm not at all experienced with regular expressions, and therefore I can't quite speak to whether or not using trees with regular expressions is good for anything more than an academic exercise.
I can think of some data that trees would be useful for. For example, if for some reason you wanted to store a 'master list' of organisms, it would make a good deal of sense to do it with a tree. The root node would contain references to Animalia, Plantae etc, each of which would contain references to sub-classications, until finally one would reach the leaves, which would be species or sub-species. However, it doesn't seem like most data would be suited to a similar representation: I can't imagine wanting to represent a list of students in a school this way, for example.
Wednesday, 23 October 2013
Sunday, 13 October 2013
Entry 1: Recursion and OOP
Object-orientated programming:
Insofar as I understand it, the primary distinction between object-orientated programming and other 'styles'(which to my recollection we have not dealt with explicitly) is the bundling of certain data with its appropriate methods into the titular 'objects', as opposed to simply writing a number of functions to use the data as you wish, while leaving it separated it from them in a mass(I assume that the methods of the non-OOPers are not as primitive in actuality). The former method seems as if it would have many advantages over the latter. Simply on the level of organisation, knowing from the structure of the code how functions(methods) and data relate would seem to be an advantage; if a change to the program was necessary, it seems to me as if OOP-styling would make it's implementation easier and its debugging more expeditious. I am not currently equipped with the knowledge to comment on how this might effect the functioning of the program itself, but I suspect the impact is non-trivial.
Recursion:
Recursion thus far has come in two flavours: recursive data structures and the recursive functions which we have written to operate on them(the latter has been the primary focus, and our of use of recursive functions has not been limited to dealing with recursive data structures). Unless I'm missing something, the nested list has been the only real recursive data structure we've encountered, and usually only really as a motivating example for the use of recursive functions. I've found writing recursive functions to be challenging and intellectually exciting. There's a certain elegance when you finally conceive of a recursive solution to a tough problem; this sense of elegance is only magnified by the fact that you often only have to write half as much code to implement it! Again, I don't feel confident making any sort of grand pronouncement as to the usefulness of recursive functions more broadly to computer science, but they seem to be the optimal approach in certain situations, especially when dealing with the aforementioned self-similar data structures.
Insofar as I understand it, the primary distinction between object-orientated programming and other 'styles'(which to my recollection we have not dealt with explicitly) is the bundling of certain data with its appropriate methods into the titular 'objects', as opposed to simply writing a number of functions to use the data as you wish, while leaving it separated it from them in a mass(I assume that the methods of the non-OOPers are not as primitive in actuality). The former method seems as if it would have many advantages over the latter. Simply on the level of organisation, knowing from the structure of the code how functions(methods) and data relate would seem to be an advantage; if a change to the program was necessary, it seems to me as if OOP-styling would make it's implementation easier and its debugging more expeditious. I am not currently equipped with the knowledge to comment on how this might effect the functioning of the program itself, but I suspect the impact is non-trivial.
Recursion:
Recursion thus far has come in two flavours: recursive data structures and the recursive functions which we have written to operate on them(the latter has been the primary focus, and our of use of recursive functions has not been limited to dealing with recursive data structures). Unless I'm missing something, the nested list has been the only real recursive data structure we've encountered, and usually only really as a motivating example for the use of recursive functions. I've found writing recursive functions to be challenging and intellectually exciting. There's a certain elegance when you finally conceive of a recursive solution to a tough problem; this sense of elegance is only magnified by the fact that you often only have to write half as much code to implement it! Again, I don't feel confident making any sort of grand pronouncement as to the usefulness of recursive functions more broadly to computer science, but they seem to be the optimal approach in certain situations, especially when dealing with the aforementioned self-similar data structures.
Subscribe to:
Posts (Atom)