Sorting and Efficiency

Ever needed to write a program to alphabetize a telephone directory, or to arrange library records by catalogue number ?  If so, the problem of arranging the elements of a list in chronological order has definitely arouse.  

As you can probably tell by the preamble, the topic of interest concerning us this week pertains to "Sorting and Efficiency."  In solving the above problem, there are many algorithms that can be used to sort a list including insertion sort, merge sort, quick sort, and selection sort, just to name a few.  Given that these algorithms vary immensely in efficiency, it is very important  that we choose a good algorithm.  For instance, consider the following list: L = [x for x in range(5000, 0, -1)].  If we want to sort this list (from smallest to largest), we could try to use merge sort or insertion sort.  Although, its quite obvious in this case, that merge sort severely outperforms insertion sort.  In general, using big-Oh notation, the efficiency of merge sort in the worst case is given by 

O( n * log₂ n ),whereas insertion sort is given by O(n ** 2).  So it shouldn't be surprising that MERGE sort outperforms INSERTION sort for large lists.

Thats the simple-essence of what I've learned during these past two weeks on sorting and efficiency.  Although, I personally understand the "practical" benefit of these tools, I sometimes find determining the efficiency of certain algorithms to be very difficult.  Take merge sort for instance.  Initially, I thought since merge sort divides the list into half, similar to binary search, its performance would involve log₂ n.  However, I was missing an n factor, and had no idea where it came from.  It took some time before I realized that the n arises from the possible splits that are done, and the depth of the recursive calls is given by log₂ n.  In fact, determining efficiency was my biggest hurdle on the second term test.  I'll definitely have to find external resources (more practice examples) to aid me in preparation of the final exam.   

Triumph

With things slowly quieting down, I think it'll be a nice time to look back upon my triumphs and struggles with A2 Part 2.
My only real struggle with this assignment was with Is_regex.  To be candid, I found the coding for this function to be by far the toughest of the bunch.  The innumerable cases to consider for possible inputs, and possible program responses took a hefty amount of time.  After I thought I had finished the code, I ran a series of test cases.  And bam!  The invalid regular expression  "(1|2)**(1)" returns True.  Then, back to the drawing board.  This process contuined a few times until it finally passed every single possible test case I could conceive of.  Following this function, the others seemed ridiculously simplistic.  Although, a lot of code that followed would not of been so simple, if not for the extraordinary work that preceded it (and yes I'm referring to Is_regex).

Design Your Regex Trees

At first glance, I was utterly confused by what our specific task for Assignment 2 part 1 was.  It seemed rather ambiguous.  I found differentiating between the design of Regex Tree and Tree to be most troublesome.  My implementation of class ParentRegexTree seemed to mimic the implementation of class Tree in lecture in almost every way imaginable.  It was practically identically structured code with a few differences.  Namely, my ParentRegexTree class had child classes.  The necessity of these child classes at first, seemed rather pointless to me.  Initially, I felt everything could be performed in the parent class, although I soon saw the larger picture.  Nonetheless, I did successfully complete my regex design employing inheritance as required.  Overall, I guess the greatest challenge I encountered on this assignment was the simplicity.  So simple it actually looked complicated.

“Life is really simple, but we insist on making it complicated.” 

-Confucius 

More on Recursion

After initially discussing recursion in lectures during Week 4, I posted a brief summary of recursion and gave the example of determinants (dated February 2 2014).  This is a continuation of that initial post.  

I won't dwell into the basic notions of Recursion again but an interesting provisional definition of Recursion may be --> Recursion:  If you don't understand Recursion, see Recursion. 

Take an example of recursion as it applies to the mathematical concept of a factorial.  For instance, 3! = 3 * 2 * 1 and 5! = 5 * 4 *3 * 2 * 1.  This leads to the following recursive definition.

0!  = 1

                     n! = n * (n - 1)! ,   for all n > 0

The first equation is the base case, and the second equation is recursive since a factorial is defined in terms of a factorial.  The python code for the factorial function can be found at the following link: http://stackoverflow.com/questions/4502429/recursive-factorial-function

Now since Week 4, we've studied Trees and Linked Lists which are recursive data structures by nature.  (Note, I discussed Trees in a previous post.)   I personally found implementing recursive code to initially be tantalizing (ok I'm exaggerating) however recursion has slowly but surely been growing on me.  I found implementing the recursive code for Linked Lists to be slightly harder than Trees, although this is probably a bias on my part.  Since the first term test, I've had minimal time to thoroughly study Linked Lists, although I hope to devote some time on Monday to mastering this concept. 

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.