Recursive Data Structures: Trees

Another week has come and gone.  I can't believe were practically half-way through the semester already.  But nonetheless heres a brief preamble of the material that was covered in lectures.  The topic of discussion this week was trees.  Trees are basically hierarchal data structures, similar to the notion of a family tree.  In the case of a binary tree, every node has exactly one parent, except for the root which has no parent.  Furthermore, each parent node has no more than two children.

As suggested by the title, trees are a recursive data structure, so it shouldn't be surprising that many recursive routines can be implemmented.  For example, questions like 'how many nodes are in this tree' or 'whats the length of the longest path of this tree' can be answered by implementing recursive code.  At first, I found the implementation of these recursive algorithms to be quite confusing.  But after throughly reading over the lecture notes, and the material covered at the following link http://openbookproject.net/thinkcs/python/english3e/trees.html, I have vastly improved my comprehension.

Namespaces in Python

Have you ever wondered where names live in python?  It may seem like a mundane question, but its an important one, and one that doesn't lack intrigue.  Basically, names in python live in namespaces, analogous to how vectors live in vector spaces.  However, this doesn't tell us much, as it only introduces the seemingly abstract concept of a namespace.  To make sense of this notion, lets discuss how python searches through various namespaces when looking for a name.  Specifically, python looks through the following namespaces in order:

(1) Local scope of the innermost function
(2) Scopes of any enclosing functions (if def was in another def)
(3) Global scope (names defined at the top level of the module)
(4) Built-in names in Python such as sum, strip, etc.

This allows python to keep organized, particularly so names outside a function def won't conflict with names inside.

While this is definitely a cool topic (well at least for me) this week seemed to be progressively slow-moving, probably because the buzz with Assignment 1 (which I can happily say I finished!!!).  Anyways, this week should be vastly exciting since we'll be studying 'Trees', literally!

Recursion

This week we spent a considerable amount of time on recursion, and implementing recursive algorithms.  Basically, recursion means that a function can call itself within its definition.  While this provides a way to solve a complicated problem in a simple and elegant way, one must be very cautious when executing a recursive algorithm.   To elaborate, a recursive algorithm must always have a base case (terminating condition), otherwise you will have an infinite recursion, and end up with a runtime error (although other errors could possibly occur).

Prior to this class, my only previous encounter with recursion was with determinants.  To explain, the determinant of an n*n matrix is computed from the determinants of several (n-1)*(n-1) matrices, and the determinants of these (n-1)*(n-1) matrices may then be computed from the determinants of (n-2)*(n-2) matrices, etc.  In this case, the 2*2 matrix serves as the base case, as it can easily be computed.  This procedure is often referred to as Laplacian Expansion. 

Object Orientated Programming

Hello, World!

With this being my first blog post I'm rather excited.  The topic of discussion in this post will be Object Orientated Programming,  often abbreviated as OOP.  Basically,  OOP deals with the manipulation and representation of  "objects."  A collection of like-objects form a class, which defines the datatype and the methods that can be performed on the objects.  In simple terms, a class is just the "blueprint" to build a particular type of object.

Now, a noteworthy concept that arises in OOP is inheritance.  Inheritance describes the ability of a class to obtain most or all of its methods from a parent class.  Interestingly, all python classes are subclasses of the special class Object.  Yet, even more remarkable is that bool is a subclass of int! This may or may not seem peculiar to you depending on your relative background in python and older versions. 

Nonetheless, I personally find OOP to be very useful.  It enables me to use the concept of a class to define new data types for a variety of purposes.  For instance, we could create an endangered animal class that keeps track of the name, species and population of the endangered animal, or a luxury car class that keeps record of the name, colour and price of the car.

I'm definitely looking forward to investigating and learning of further concepts related to classes, including other special methods, multiple inheritance, trees etc.  Not to mention that I'm rather excited to learn other object-oriented programming languages, particularly C++, upon mastering python.  Overall, OOP is not only efficient and cleaner, but allows the programmer to write beautiful code!!