Lecture of 28 Oct: Binary Search Trees

Today in class we began to cover binary search trees, binary trees in which the left child of each node (if present) has a value less than that of the node, and the right (if present) one greater than it. We covered some of the operations that one might want to perform on such trees, such as the insertion or deletion of nodes, as well as the necessary helper functions that, for example, return the largest value in a given (sub)tree. We have not yet gotten to what seems to be the primary motivation for such trees' existence, efficiently searching through them for a given value, but it seems to be a simple recursive function that can be easily implemented.

Although these trees do make some things slightly easier, I am not yet convinced that they really help. They appear to me to not be conventional forms of input, rather they are data types created and used to make the programmer's job easier. But if the task is (for example) searching a list (or other iterable) for an element, it seems counter-intuitive to first convert the list into a binary search tree, then search that tree, then locate the found node in the list, rather than simply using a recursive algorithm on successively smaller splices of the list. However, I suspect that there are other benefits to using binary search trees that remain to be seen, and that they are indeed the natural and best representation of some data. Time (and future lectures) will tell just how effective these trees can be. For the time being, they remain an interesting exercise in linked data types and recursion.

And now...: Recursion

(for more information, see here)

So now onto the recursion post.

Recursion is a process which repeats in a self-similar way. A recursive function calls itself within its definition to achieve the desired result. To prevent the program from falling into an infinitely deep hole, the function will do something else in a few specific cases. It is appropriate to use a recursive approach to solve a problem if the problem can be easier solved by solving smaller versions of the same problem. For example, with a three-peg Tower of Hanoi problem, if the programer recognizes that to move n disks from one peg to the next he must move n-1 disks to a third peg, then it becomes obvious that a recursive approach will be useful, since the solution involves solving problems smaller in scale. Recursion is a deceptively simple concept that makes it easy to solve potentially very complicated problems, although one that can be quite frustrating to trace and de-bug if something goes wrong!

Thanksgiving, Turkey Comas, and Object Oriented Programming.

So with all the excitement over being done the assignment and looking forward to a long weekend it seems that I forgot to start writing in this blog.

During the long weekend, I ate way too much sweet potato and entered a sedentary, slug-like state, moving only to raise or fold in the thanksgiving tradition of poker with Grandma. Finally back in Toronto, unpacking the suitcases of clothes I brought home to launder, and preparing to go to the library with a stack of midterm study materials to have a nice nap, I remembered with a start that I had to write a post for the blog about OOP. Oops! So here goes:

Object-oriented programming is a programming paradigm which focuses on bundling together functions, attributes, and methods into objects such as classes. This builds a model in the computer closer to the real-life representation of what is being dealt with than other paradigms such as procedural programming. This allows programmers to think of dealing with these virtual objects as they would ones in the real world, making it simpler and more straightforward to implement new methods and functions within the object or to use the objects in new ways. If, for example, there is an instance of the class 'Car,' then a program need not manually change the attributes of the car to drive to a place; the program can simply call the car's 'drive' method, similar to how a driver does not run time forward, teleport his car to the destination and then adjust the gas and odometer readings to something sensible; he simply puts the car in gear and drives where he wants to go. Treating the car as an object ties all the dials and controls of the car together, making them compose as detailed a model of the car as the program requires, which helps organize a computer scientist's thoughts and analysis of the program, as well as making the code be more comprehensible and easy to modify to other programmers.