Week 11: Sorting and Efficiency... and BOGOBOGOSORT

Sorting, sorting, sorting...  First of all, what is sorting?  Well the idea is really simple, sorting is just taking a collection of elements and putting them in order, according to some trait be it length, size, value, etc.  What makes it an interesting computer science is not what sorting is but rather HOW we sort, what algorithm or set of rules we follow to sort.  There are numerous types of algorithms, and generally we can say the "best" algorithm is the most "efficient", that is, the one that takes the least amount of time to sort a given set.  However, due to the varying types of set we are given, it is generally true that there is no "best" algorithm, although certainly there are _better_ algorithms.  To see the varying efficiency of different algorithms on different types of shuffled sets, you can play with this animation: http://www.sorting-algorithms.com/.

You will note that there are several different types of algorithms outlined in the linked animations.  Let's try to understand some them and how efficient they are (to help you understand I will link to folk dances on youtube that model different sorting algorithms (seriously check these out they are great))!

Bubble Sort:  

https://www.youtube.com/watch?v=lyZQPjUT5B4
(1) Starting at the beginning of the collection, go through the entire collection and swap consecutive pairs of elements if they are out of order.
(2) If no swaps occur, the collection is sorted, otherwise, go to (1)

Bubble sort is a simple algorithm in principle.  However, it is not terribly efficient.  In the best case scenario, bubble sort passes through all n elements of the list once, and has O(n) efficiency, otherwise it passes through all n elements up to n times and has O(n^2) efficiency on average, and in the worst case.

Insertion Sort:

https://www.youtube.com/watch?v=ROalU379l3U

(1) Consider the entire collection unsorted.
(2) Move the first element of the unsorted section into the sorted section, inserting it where it must fit by comparing it to the elements of the unsorted section until it is larger than an element.
(3) If there are no more elements in the unsorted section, the collection is sorted, otherwise, go to (2)

Like bubble sort, insertion sort has O(n^2) efficiency on average and in the worst case, and O(n) efficiency in the best case.  However, since less comparisons need to be made for each pass than in bubble sort, it is generally more efficient.

Selection Sort:

https://www.youtube.com/watch?v=Ns4TPTC8whw
(1) Consider the entire collection unsorted.
(2) Move the smallest element of the unsorted section into the sorted section by comparing all the elements in the unsorted section to a temporary "smallest element" and replacing it if a smaller element is encountered.
(3) If the unsorted section is empty, the collection is sorted, otherwise, go to (2)

Selection sort passes through the entire list n times and makes n + (n - 1) + (n - 2) + ... + 1 comparisons no matter what.  It has O(n^2) efficiency in all cases.

Merge Sort:

https://www.youtube.com/watch?v=XaqR3G_NVoo

(1) Split the collection into two sections.
(2) Merge sort each sub-collection.
(3) Combine the two sorted sub-collections.

This sorting algorithm uses the magic of recursion.  It essentially splits the collection into n pieces and the puts them back together.  It has O(nlogn) efficiency in the worst and average case.

Quick Sort:

https://www.youtube.com/watch?v=ywWBy6J5gz8
(This dance is my favourite)
(1) Pick a pivot element from the collection (in the dance, this would be the black hat)
(2) Move all the elements smaller than the pivot into one sub-collection before the pivot and all the elements larger than the pivot into another after the pivot.  The pivot is now sitting in its final position.
(3) Quick sort the sub-collections.

This sorting algorithm also uses recursion.  Again there is splitting of the initial collection into n pieces, however, once split out of the sub-collections, each pivot is now in its final position.  Comparisons are made for each element to the pivot for each pass of quick sort.  It has O(nlogn) efficiency on average, and is (generally) faster than other O(nlogn) algorithms.  This however depends: as in the animations we see that when there are lists containing several non-distinct elements ("few unique") quick sort performs much worse than merge sort.

To read more sloggy material on sorting algorithms, check out this slog: http://slogmyblog.blogspot.ca/, which describes in more detail an efficiency measuring notation I've used, known as "big-O".

FINAL (slightly off topic) NOTE:

This week's slog is brought to you by, bogobogosort the best worst sorting algorithm ever.

A few years ago, I took a one day class on sorting algorithms, and at the end of the day, we were divided into teams for different algorithms and raced see which algorithm was "most efficient" by trying to sort a set of cards with numbers.  I was part of team bogosort.  

Bogosort is a sorting algorithm sometimes known as Monkey sort.  The idea is pretty simple: 

(1) Shuffle the set at random.

(2) If the set is now in order, you are done.  Otherwise, go to (1).

Bogosort has O(n!) efficiency on average (since it is simply a probability calculation).

As you can imagine, although team bogosort failed miserably at actually sorting our set of cards, we arguably had the most fun, throwing them in the air and checking to see if they were in the correct order.  Although I am impressively fond of bogosort, I discovered (during extra time during lab) the magic of bogobogosort, which takes all of the randomness of bogosort and makes far less efficient.  If you want to read more about bogobogosort (which I'm sure you do!) you can check out: http://www.dangermouse.net/esoteric/bogobogosort.html, which provided me personally with much joy.  

Week 10: Regexes? Regexs? Regexis? Regex?

Seriously, what is the plural of regex?

About half an hour ago, assignment two was due!  Finishing up part two was fun.  Here are some thoughts regarding the second half of the second assignment, and the challenges it brought to the table.

Challenge 1: finding the right '.' or '|'.

In many of the functions, it was necessary to divide a regex string into two sections, at the right '.' or '|' in order to find the subtrees.  How did I end up doing this?  By splitting at '.' or '|' and then using the indices given by those splits, checking for equal numbers of open and closed parenthesis before the split to see if the index was correct.

Challenge 2: error checking in permutations.

I'm not sure that this issue was actually conceptually challenging, all I know is that it took much longer than it should have to find all the mistakes.  Incidentally there were 5.

Challenge 3: matching dottree.

Matching dottree was challenging.  However it was significantly less challenging once I figured out that it sufficed to create a helper function which returned all the possible ways to split the given string into two separate strings.  Then I just had to check to see if at least one of them was correct.

Challenge 4: how many doctests is too many doctests?

Throughout the writing of this program, I used doctests as I went along to check every basecase for every function.  This testing (which I did quite thoroughly since I wanted to catch any possible tricky exception) was rather extensive.  I wasn't sure whether or not it would be appropriate to include so many...   But I figured they couldn't hurt.

With that, assignment 2 was completed and submitted.

Marks for assignment 1 just appeared and I am quite happy about those results.  Next week there's a midterm.  I really wish there were more practice tests posted for such things.  It really feels like this course is all over the place sometimes.

Week 9: Treeeeeeeees

So, trees are fun!

Why are trees fun?

Because they have subtrees which are fun!

Why are subtreees fun?

Because they have subtrees which are fun!

...

Because they have leaves which are fun!

If you couldn't tell, I am trying to convey the idea that trees are recursive.  In math land, trees are graphs containing no cycles.  In CS land, they are data structures which can be described recursively.

Usually, the structure of trees are something like the following.  There's a root which is a base node for the tree (think trunks).  Then from this root (or trunk) the tree can have children (think branches) which we can call subtrees (ever notice how branches can look like small trees?).  Then from these subtrees we can have more subtrees, but eventually, some subtree's subtree is what we call a leaf (LIKE A REAL TREE), which is basically a node with no children.  There are lots of different kinds of trees, since theoretically they can have as many or as few children as you want them to.

So far in CSC148, we have been working a lot with trees, since (I'm guessing) they are such an excellent way of practicing recursion.  I think I have been mostly quite comfortable with them, and I'm really enjoying the exercises and labs.  As I said previously, trees are fun!  I think really, CS is a practical thing to learn, that is in order to understand it, you really have to just write some code yourself, which is why the labs and exercises and assignments are the most effective teaching tools, in my personal opinion.

To read someone else's opinion of trees, you can go here: http://iloveslogs.blogspot.ca/2014/03/trees.html! How fun!!

P.S. Happy pi day!

Week 8: Assignment 2 Part 1

This past week has been mostly uneventful, save the first part of the assignment.

The lab went very well, my partner and I finished all of the work, including all the bonus material with a half hour to spare.

The assignment was more interesting.  As usual, it took a while to wade through the assignment handout and figure out what exactly I actually needed to do.  Once that was done, it took some more time to figure out how I was going to structure my trees.  In the end, I had two main bodies of code, a basic regex tree from which leaf and star trees inherited most of their code, and dot tree, which inherited from the basic regex tree and was inherited by bar.  After much testing, things finally seemed to work so I submitted my assignment, then realized I forgot to check it with pep8 so resubmitted a much prettier version.

It took me a while to figure out how to make the attributes of the various trees only settable during initialization.  Thanks to piazza and past materials, I was able to find the example from class and that was fine.

Other than that, there's not much to talk about.  In the future I will write a more in depth slog about trees, but for now, I'm looking forward to this coming week and a new exercise.

Week 7: The Official Recursion Slog

So by completely misreading the calendar, I accidentally assumed that last week was week 7, and as a result wrote an entire slog pertaining to the topic of recursion.  The good news is that there's plenty more to talk about regarding this topic.

So first of all, I'd like to go over the overarching idea of recursion, and one of my favourite examples.  As I said last week, recursion is like reverse induction.  Instead of starting with a base case and then the general case, recursion begins with a general case and reduces it down to a simpler problem.  With every recursive step, the problem gets closer to being solved.  Too often have I heard examples of recursion using the idea of infinite recursion.  While this idea has its place and is certainly very pretty (especially in proofs and fractals), it does not actually encompass the idea of using recursion in programming.  The idea in programming is not to use recursion indefinitely, it is do use it a finite number of times in order to derive an answer of some form.  If your recursion never stops, that's called an error.  Which brings me to my favourite example of solving a problem using recursion, one that is quite simple, but captures the essence of the use of recursion quite well.

Imagine you are sitting in a movie theatre of logicians.  You do not know how many rows there are in total at the theatre and it's far too dark for you to count the number of rows in front of you.  You do know that your row number is one more than the row in front of you, and so does everyone else in the theatre.  How do you figure out your row number?  The recursive solution is not hard to figure out.  Ask the row in front of you for their row number.  You know your row is one more than that one.  If they do not know the row they are in, they can ask the row in front of them, who can ask the row in front of them, who can ask the row in front of them, until this chain reaction of asking reaches the first row, who can clearly see that they are in the front, row 1, best seats in the house.  So row 1 tells the next row "This is row 1" and row two has the difficult task of adding 1 to that number and telling row three "This is row 2" and so on.  This continues until the girl or guy in front of you turns around and says their row number.  You also add 1 and VOILA! You know what row you're in.

In this example, we have the base case: row 1, and the recursive step: if not in row 1, ask the row in front of you for their row number; a simple, logical recursive solution that takes a problem and reduces it to a slightly simpler problem with every step.

As I discussed last week in my slog, while easy to code and to understand, recursion can be somewhat inefficient.  In the comments, another slogger linked to an interesting stackexchange question, where I extracted this quote: "In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame." This succinctly summarizes the idea of recursion and efficiency as is described in last week's slog and explains in part, why Tour of assignment 1 got to be quite slow as the number of cheeses got bigger.

And now a couple of sentences on how I feel about recursion.  I like it.  It's quite interesting to use.  It makes for some pretty and clever code.  If you want to read more about recursion, you can either a) look at some of the previous posts of this slog or b) read this slog: http://csc148sloggingalong.blogspot.ca/2014/02/rec-i-got-it-sion.html which is a rather entertainingly written piece on the whole notion of recursion.  I particularly enjoyed the section subtitled "Is recursion useful?".