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.