Assignment 2 part 2 delimma

Binary search

Binary search is a neat algorithm that finds a certain key in an array of keys in a dictionary.  We have already been introduced to this in CSC108 and it is refreshing to come across something familiar every now and then.  However, my knowledge as it turns out is very basic.  The example we did in class was a little confusing but I think after writing it down on paper it has become much clearer.   From now on, pen and paper it is!

Trees and Linked Lists

This week we learnt about the concept of linked lists which has certainly been one of the most challenging topics to grasp.  I found the lab assignment quite difficult to do although I had been quite confident of my knowledge of trees, which I thought were similar to linked lists.  Apparently, I wrong.  Thanks to the clear explanation posted under title of "Binary Search Trees and Linked Lists" on http://courseblog148.blogspot.ca/ I am now a little more confident of my knowledge about both principles.

A binary trees largely resembles a regular tree, or a family tree.  The top part of a binary tree is called "the root" in regards to the tree analogy, or the "parent" when considering a family tree.  Each "box" in a binary tree has certain features.  It has a "cargo", "left", and "right".  Each box branches off to point to the other boxes, if available.  Left and right are the children pointing to the following boxes.  The default value of the left and right children is None; when no preceding boxes are found.  When left and right are both None, the whole box "child" is said to be a leaf.

Diagram of a binary tree.

What might be confusing to some, myself included, is that linked lists largely resemble binary trees in their arrangement and general structure.  However, linked lists do not have left and right children; they occur when a parent only has one child to point to, which is in the form of a list.

 Diagram of a linked list.

Recursion

There are a few principles in computer science that never fail to astonish me, one being recursion.  I was intrigued from the first time I heard Professor Heap mention the concept.   The reason I found it fascinating is because I had not expected the existence of a sneaky method as such that so cleverly uses the idea of a problem within a problem.  Recursion is the term given to the method used to solve one bigger problem by systematically approaching the solutions of smaller instances of that problem.   In other words, recursion occurs when a function calls itself a number of times until it reaches the solution it seeks.  One may think of this approach as a close relative of mathematical induction.  The beauty of this method is that it follows our own way of thinking; we like to break problems into smaller, more manageable parts.

A key to designing a successful recursive method is to include a base case; a condition to stop recursion hence preventing it from going to infinity.  Using the following example, it is easy to understand that function “get_factorial” uses itself to return the n factorial of consecutive numbers until it reaches the number 0, which is the termination condition.

 Having used the principle myself, I can say that there are both positives and negatives to this approach.  Recursion is often a preference by many programmers as it makes code clearer, simpler and more “elegant”.  Although recursion may be easier to handle, especially with transversing trees from the human end, I find that it is generally slower and takes more stacks and hence memory than more standard means of computing.  All in all, it seems that the nature of the problem eventually determines the most ideal method of computing.

Trees, labs and prep for midterm

I found this week's lab crucial to the understanding of the material covered thus far.  The problems really helped me revise for the midterm coming up in less than two weeks.  I noticed I was a bit weak with the principle of ADT.  I am going to repeat the examples we've covered thus far in class, and maybe drop by office hours before it's reading week!

Tracing the problem

This week has been no walk in the park!  I am a little ashamed to say that I was having some trouble understanding basic concepts in this course, like tracing.  At times, I would simply stare at the slides during lectures, trying to comprehend what is being said.

It has been a milestone for me to actually seek help this week, mostly because I tend to like doing things on my own.  I headed over to the Help Centre after trying to spin my head around an example we did in class, and I am glad I did.  As it turns out, tracing in recursion is not very different from the tracing we used to do in CSC108, and as the TA pointed, practice helps in this case.  I have spent the entire weekend, without exaggeration, working on various examples some of which were covered in class, and some new ones I found online.  In all honesty, I have had so much practice that I can proudly say that tracing has become almost second nature to me!

Test, Test...Revelation!

I usually try to have a positive outlook on my academic life yet it is only the 4^th week of the term and everything has already started to pile up and get more complex.  However, it does help to remind myself how much I like a good challenge!  I look forward to the lab section of this course because my lab partner and I tend to stumble upon little tips and secrets here and there as we figure out the problems given to us.  What we discover usually helps me tremendously in comprehending the material during the rest of the week. 

 This week for example, we were working on classes, subclasses, inheritance and testing of code.  As we unravelled bits and pieces of the code, we followed the logic we usually use and then we reached the step where writing a testing method was necessary.  Contrary to what we thought was a basic problem, my partner and I faced a dilemma that had us blankly staring at the screen for over 20 minutes.  As instructed, we had created a subclass in unittest.TestCase then we wrote the test methods and gave them logical names that easily referred to their purposes.  As we ran the program though, the tests simply didn’t run!  We double-checked the syntax of our code, we asked for the TA’s help, and then out of despair, we even re-wrote the entire thing with a fresh start.  But we still couldn’t pin it down.  “What are we doing wrong?”   Little did we know that a testing method in a subclass of unittest.TestCase had to start with the word ‘test’!  In other word, the name of the method must be in the form testName, where “Name” is whatever you wish to call that function.   This was especially fascinating to me because I never thought that a function’s name could have an effect on its running abilities!