Week 12: Glorious Finale

This is the last week of my slog writing.

I'm not really sure what's left to say, so here are some reflections on the course overall.

Overall, I think the course was good.  Decent.  Quite nice.  I learned some.  The assignments were fun.  The lectures were quaint.  The exercises were good.  The first test was more stressful than difficult; the second test could have been shorter.  The labs were entertaining.  The slogs were... well, considering what you were reading, I'll let you be the judge of that.  

I feel like compared to my other courses, this has been a lot less stressful.  And currently, I'm debating whether or not to take more CS classes.  I feel like it's a definite option, and a good one at that.  

With the exams coming up, I am preparing to study quite a bit.  However, seeing as how I have other exams to worry about first, I don't feel like this one is a pressing issue.  That being said, I do think I should look over some of the notes about efficiency.  If I'm giving off the impression that I'm not terribly concerned, please keep in mind that what I'm really say is that I'm not concerned yet.

Anyways, I'm glad I took the course.  I feel like I certainly have a better understanding of CS, at least the small portion of what we've uncovered in this course.  And since I'm not sure I have much else to say, here I am signing off.

So that's it!

No more slogs!

Have a great day!

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?".

Reading Week: Thoughts on Recursion!

For this past week I haven't been up to much CS on account of a significant pile of math homework.  However, I still have had time to think about the midterm as well as recursion, a rather interesting topic.

The first time I had recursion explained to me, it was somewhat confusingly done with matryoshka dolls (those russian dolls made of wood, in increasing sizes where opening one reveals another).  The second time was more concise: "A recursive function is one that calls itself."  In a computer science context, this explanation made a lot more sense.  Like induction, recursion calls for a base case: unlike induction however, it is more like a final stage instead of a first step.  In this sense, recursion takes a large problem and continues to reduce it to a slightly smaller problem, until it reaches the base case and can be solved.  There's a caveat to this however, a function which employs recursion may not be the most efficient, since it has to go through every previous case.  In our Towers of Hanoi assignment, I certainly noticed this.  Because of the degree to which Tour.py relied on recursion, its efficiency was rather questionable (this of course, may be a result of my inability to code efficiently but I'm going to attribute it to recursion for argument's sake).  Despite this, recursion certainly makes the code easy to read and to understand, and it was really the only way I could think of to code the assignment.

In my experience with math, I've seen recursion come up in the definition of some very pretty fractal pictures, I'm even guilty of making a Menger Sponge cake (second iteration, made of many tiny delicious cake cubes held together by cream cheese icing).  To learn about the use of recursion in CS has been very interesting for me.  I can appreciate its usefulness very much.

I'm (not) looking forward to the midterm this coming week and I feel totally (not) prepared!  Here's to NOT failing.