Sorting and Efficiency

Efficiency, Big-O

It is important to be efficient, not only in everyday life, but in computer science as well. Being efficient means that you 'achieve maximum productivity' using as few resources as possible. For computers, we want to try to solve problems by implementing algorithms which use as few resources (such as memory) as possible. How can this be accomplished? It is done by analyzing the implementations of computer programs, and determining whether or not a problem can be solved in a simpler, more efficient manner.

Credit to: http://arizanagallery.blogspot.ca/2011/05/how-to-maintain-quick-brain-memory-loss.html

In this course, our focus on the efficiency of algorithms relates mostly to the implementation (the code itself).

We often use the notion of Big-O to describe the runtime of an alogrithm. Big-O is described loosely as an upper bound on the runtime of an algorithm. Here is an example of Big-O notation:

def thing(L):

    

    count = 0 

    for i in range(len(L)):

        if L[i] == 1:

            for j in range(len(L)):

                count += 1

    

    return count

from time import time, clock

L = [1]*1000        #length of list here is 1000

start = time()

thing(L)

print("Time elapsed for thing: {} for {} items".format(time() - start, len(L)))

Since there are two for loops in this function, we expect this function to be O(n^2). What does this mean, though? Well when I run this program with different lengths for the input L, I receive these outputs:

Time elapsed for thing: 0.14109086990356445 for 1000 items

Time elapsed for thing: 1.0326859951019287 for 3000 items

Time elapsed for thing: 3.1200690269470215 for 5000 items

Since I said this algorithm was O(n^2), I expect that when I triple the size of the list L, the function should take 3^2 = 9 times as long to run. Similarly, when I multiply the size of the list L by 5, the function should take 5^2 = 25 times as long to run. The data above seem to support this theory.

However, this algorithm will not always have quadratic runtime. If the if statement fails every time the inner loop gets executed, the algorithm will have linear runtime. This is why Big-O is only an upper bound, it does not tell you that all inputs will have runtimes which grow in a quadratic manner.

Sorting Algorithms

In this course, we learned about some sorting algorithms which are better than the basic Bubble Sort, Insertion Sort, and Selection Sort. These are Quick Sort and Merge Sort. Quicksort works by choosing a 'pivot' and partitioning the entire list into 2 lists, where one contains all items greater than the pivot, and the other list contains all items which are less than the pivot. It then recursively sorts both lists. The base case is a list of length 1 which is already sorted. 

Quick sort on average, is O(n log n). The log n part comes from the fact that we have to choose at least log n pivots to partition the list into 2 parts. The n factor comes from the fact that we have to compare each item in the entire list to the pivot, which requires about n comparisons.

Quick sort may have O(n^2) performance in its worst case. If the pivot chosen does not partition the list into 2 even sections every time, it is likely that more than log n (but no more than n) pivots will be chosen.

Merge sort always should have O(n log n) performance. It always operates the same way each time, by splitting the list into parts, until each part has only 1 element in it. Then, it re-merges all these parts together. The log n part comes from the fact that we make log n 'splits', and the n factor comes from the fact that we need to make n comparisons for the merging process.

Even though n log n < n^2 for large n, it is not certain that algorithms with O(n log n) performance will always outperform algorithms with O(n^2) performance. It is only more likely that they will for large n (inputs of large size). As seen below, when n is small (such as n < 10), algorithms which grow quadratically or even exponentially outperform the log n algorithm. But of course when n is very large, the log n algorithm 'wins'.

Credit to: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/

Another thing to consider is whether the elements in your list are close to being sorted or not. For example, if you choose your pivot in quick sort to be the first element in the list all the time, then in an almost sorted list, the algorithm will have to choose more than log n pivots, which will decrease the performance of quick sort.

So, it would make more sense to either use merge sort in this situation, or find a way to tweak quick sort so you don't run into this problem.

Conclusion:

Efficiency of algorithms should not be overlooked since it can be difference between a program running in 10 seconds vs. a program running in 10 minutes. Although we are concerned with how long a program takes to execute, we are more concerned with how an algorithm performs when the size of the input increases. 

assignment 2, Lecture material

Assignment 2 is complete, and I feel pretty good about my work for part 2. I think I managed to get all the functions to work properly (i.e. pass most or all possible test cases). The hardest parts of A2 Part 2, in my opinion, were: figuring out how to find the root of a RegexTree, and the function regex_match.

Finding the root of a RegexTree was important, since I used the algorithm for locating the root of a RegexTree 3 times in my regex_functions module. The root is either a dot or a bar (assuming the tree is not a leaf or a star tree). Locating the root is useful because it allows you to accurately split the tree into a left and right component. This allows you to use recursion on the left subtree and right subtree of the given root.

Regex match was also somewhat difficult. For star trees, you have to split the string s as:

s = s1 + s2 + ... + sk and check that all parts of s match the RegexTree r. However, there are so many ways to split a given string that this task seems almost impossible.

Thanks to Danny Heap's week 10 slides, an equivalent way to match star trees is to use the following algorithm: split s = s1 + s2. Then check that both s1 matches r, and s2 matches r*. s2 has to be a shorter string than the original string s (or else you will have infinitely many recursive calls). The base case here is the empty string, which should return True if the string s is empty. Now, you only have to check '2' possible ways to split the string s.

In other news, we have been looking at various sorting algorithms in lectures recently. Specifically, we have talked a bit about merge sort and quick sort. These are 'divide and conquer' algorithms since they involve dividing a list into half on each pass, making them more efficient than the sorting methods we learned in CSC108, like bubble sort and insertion sort.

One thing that surprises me is how many sorting algorithms actually exist. It is weird to think that there actually exist around 20+ ways to sort things...
http://en.wikipedia.org/wiki/Sorting_algorithm

Assignment 2 and Other stuff

I am very busy right now. I've got 4 tests next week in the span of 3 days, and a CSC148 assignment due next Thursday. Also, I have exercise 3 due this Thursday.

Luckily, I have already worked on Exercise 3 and Assignment 2 (part 2) and have made considerable progress already. Exercise 3 was quite challenging since it took me several hours to complete. At times I wondered whether or not I was even capable of completing it, but thanks to sheer will and determination, I was able to complete it. It feels great when your code works! But, it feels terrible when it doesn't...

So far, I have about half of assignment 2 part 2 completed. Again, it took me quite some time to figure out how to write the functions, but I eventually figured it out. Struggling through exercise 3 and assignment 2 made me realize that in order to solve these computer science problems, you need to be completely focused or else you won't be able to get anything done. Also, you need to be ready for failure. Very rarely do all your test cases pass on the first try, so you need to be patient and figure out where your bugs are, and not panic or else you will stress yourself out even more. 

Something I've learned throughout this course is learning how to use the wing debugger. I used to not use the debugger at all, but now I occasionally use it (with some success). 

As I write this, I am feeling quite stressed and nervous about the next month. I enjoy this course and I am definitely motivated to learn more in this course, but my 4 other courses are temporarily hindering me from working on CSC148 related things. I feel pretty good about my results in this course so far, so I hope I can keep up the good work.

Recursion

Recursion: 

Overview:
Recursion is a problem solving method which involves breaking down a problem into sub-problems. These sub-problems should be able to be solved in the same way as the larger problem. Usually it is a process where a function calls itself while inside the function, sort of like that movie Inception.

Credit: http://icannotdraw.thecomicseries.com/comics/25/

Why would we ever want to call a function inside of itself?
Here is a simple example:
A factorial is the product resulting from repeated multiplications. Specifically, if n >= 0, then
n! = n * (n-1) * (n-2) * ............. * 3 * 2 * 1.
We can break this problem down into sub-problems. Note that n! = n * (n-1)!
But then, (n-1)! = (n-1) * (n-2)!, and so on. Eventually as n decreases, we will reach 1, where we have to stop. (the base case)
Basically, in order to obtain n!, simply multiply n by (n-1)! By the definition of factorial will then compute (n-1)! by computing (n-1) * (n-2)! factorial, and so on.

Here is the code:

def factorial(n):
     '''Precondition: n >= 0, and 0! is defined as 1.'''
     if n <= 1:
          return 1
     else:
          return n * factorial(n - 1)


Here is another example:
The fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ....
is where each number in the sequence is the sum of the 2 numbers before it.

Let's say we wanted the 5th term of this sequence. The 5th term is the sum of the 4th and 3rd terms. Assume we did not know the 4nd and 3rd terms. We can still get their values by using the same algorithm: For the 4th term, this is the sum of the 2nd and 3rd terms. For the 3rd term, this is the sum of the 1st and 2nd terms. Once we run into the 2nd term, we can't say that this is equal to the 1st and 0th term, since this does not make sense. So, we define the base case as: if the term, n, is less than or equal to 2, simply return n-1.

Here is the code:
def fib(n: int):
     if n <= 2:
          return n - 1
     else:
          return fib(n - 2) + fib(n - 1)

Visually:

Advantages/Disadvantages of Recursion:
The factorial program can be written using an iterative process, with loops.

def factorial(n):
    if n == 0:
        return 1

    acc = 1
    for i in range(1, n + 1):
        acc = acc * i
    return acc

However, there exist problems that cannot easily be solved using simple for/while loops. For example, I am not aware of a simpler algorithm that computes fibonacci numbers. Problems like Towers of Hanoi are made much easier using recursion. In Computer Science, trees and linked lists are useful for storing and manipulating data. In order to access the data in trees and linked lists, it is easier to use recursion because trees consist of subtrees, and linked lists refer to other linked list objects making them recursive in structure.
For example in lecture, binary trees were able to be 'traversed' easily using techniques like inorder, preorder, and postorder traversal. These traversals are much easier to implement (1 to 2 lines of code) than any other non-recursive solution you can think of.

Some drawbacks of recursion:
Recursive algorithms can be slow. For example, when I try to move 30 cheeses using 4 stools (from Assignment 1), python took several minutes to compute the solution. Another problem is the usage of memory. If I want to compute factorial(2000), I get a 'maximum recursion depth exceeded' error.

Also, recursive functions can be difficult to write :(

Thinking about Recursion:
How do you know if a recursive algorithm works? Well, you have to have faith! (Sort of)
If I know a recursive algorithm works for the simplest case, I can assume that the algorithm will always work
on any instance of the simplest case.
For example, if I want to calculate the sum of [1, 2, [3, 4], 5], and I know that my summation algorithm works on flat lists (a list with no nested lists), then I can assume my algorithm work on any number of nested lists.

Personally, I relate recursion to mathematical induction. If I know that P(1) is true and I know that P(n) implies P(n + 1), then I can conclude than P(n) is true for all n > 0.

Similarly, if I know that an algorithm works on the simplest case (base case), and I know that the algorithm will work for some higher level cases, then I can reasonably conclude it will work for all cases.


Closing Remarks:
Before this course, I was uncomfortable with recursion. Although I was able to trace code and follow the lectures, I struggled to write recursive functions. Over the past few weeks I feel more confident in my abilities due to hefty amount of time I spent practicing recursion. One of the main problems I had was over-thinking the problem. Sometimes I would trace code too deep, or I would write a function in 5+ lines which actually could have been completed in 1 line using techniques like list comprehensions and ternary if.

Test, Linked Lists

Test 1 was written this week. I did not find any parts of the test particularly difficult, but I do know that I made some small mistakes on the last question about stacks. The question asked to implement a 'dividing stack' class which would only allow you to push items onto the stack if the new item evenly divides the previous number in the stack. In my solution, I called the wrong method: I used self.push(n) instead of Stack.push(n). However, I do believe the structure of my solution was correct (I even tested it myself..). As for the rest of the test, I feel confident that I did well. In particular I think I answered the recursion / tree question correctly, which is great. Of course, I may be completely be wrong so I guess we will have to wait and see.

This week in lecture and in the lab, the topic was linked lists. The lab was frustrating because I was not able to implement a queue using linked lists. I feel like I understand the basics of linked lists - each node has a value (a head) and a reference to its link (rest). But, in the lab I could not figure out how to remove the first element in the queue. The lab handout says we should have 2 attributes: a reference to where you add new LinkedList elements, and a reference to where you remove the oldest LinkedList element. I am not quite sure what this means. My attempt at a solution was to simply have the Queue class hold 1 attribute, a LinkedList object. In order to find the oldest LinkedList element, I tried to use a loop that stops once it reached a LinkedList whose 'rest' attribute was an empty node (i.e. LinkedList()).

So far this has been the only lab that I felt completely lost in, so I will try to re-work the lab this weekend and try to approach the problem in different ways.

I am trying to get better at recursion!

I spent a couple of hours studying recursion, as it seems to be a weak point for me right now. In order to this, I went back to the week 4 recursion lab and re-worked through the problems. Also, I went back to some of the class examples.

I believe one of the problems I have is that I over-think the problems. For example, I was working on the problem of trying to reverse a string. My first attempt at a recursive solution was to create an accumulator that would hold the last letter of the string. Then, if the string was one character long, I would return only that letter. If the string was longer, I would re-call the function using the current string, minus the last letter. The code looked like:


def rev_string(s: 'str') -> str:

    new = ""
    if len(s) == 1:
        return s
    else:
        return rev_string(s[:-1])


This is clearly wrong because obviously my accumulator variable does nothing. I end up returning the last letter of the string s, because I am not actually adding on letters to my accumulated string, new.

After some thought, I realize that the function I was trying to write practically writes itself. For example, if I want to reverse a string, I simply take the last letter and add the reversal of all preceding letters:


def rev_string(s: 'str') -> str:
 
    return s[-1] + rev_string(s[:-1]) if len(s) > 0 else s


Not only does this function work, it looks a lot simpler.
Brief explanation on how it works:
If the string, s, is longer than a single character, take the last letter of s and add the reversed string of all preceding letters (by calling the function recursively).
If the string, s, is only a single character, simply return s. (This is the 'base case')

For example, if I want to reverse 'asdf', I want to take the last letter 'f' and add rev_string('asd').
But rev_string('asd') gives 'd' + rev_string('as'), and so on. So, the final return value ends up being
'fdsa', as desired.

This was sort of a long post on a seemingly easy example, but recursion was something that did not come naturally to me.

Week 6 - Trees and a1

Assignment 1 is finished. I had to do some last minute fixes to my code which was a bit stressful but I'm glad it is finally done.

This week in lecture we covered trees. This is an ADT that is interesting to me because it is almost entirely a recursive data structure. When I look at the tree implementation code, it looks very simple and elegant because there is very little code you actually need to write. However, it would be quite difficult for me personally to come up with the tree implementation on my own.

So far I don't know where I would use trees in practice. Perhaps they are used to represent information in a hierarchical manner?

The week 6 lab was the easiest lab so far. It only required us to complete a few functions and write some test cases which was not difficult at all, although I guess I need to practice writing unit tests because I always forget how to write those.

Unfortunately assignment 2 and test 1 are coming up so I can't relax too much during reading week...