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.

Week 6: Assignment 1 is DONE!

My main focus this past week has been working on finishing Assignment 1.  Having completed TOAHModel.py and ConsoleController.py, I was left with the most interesting part of the problem: figuring out how I was going to code Tour.py and optimize my cheese stacking strategy.  The most important step of this was, of course, figuring out a way to find the elusive i, the variable that optimizes the Towers of Hanoi for four stools.  At first, I attempted to try to find some pattern, but then decided that my complete inability to do computations (perhaps inability is inaccurate, and a strong aversion is more correct) meant that a different solution was suited for me.  I read a slog that has a computational solution to i that you can check out here: http://liamsslog.blogspot.ca/2014/02/week-5-tower-of-hanoi.html.  In the end, I thought about how the simplest way to define the Fibonacci sequence is simply to define it recursively, and then proceeded to question why in the world I would define this sequence differently.  I simply used the formula provided in the handout, and found the minimal number of moves for each number of cheeses.  Then I returned the i that corresponded with that minimal number.

The next thing was to simply use the function provided in class for three cheeses to recursively define a function for four cheeses, as indicated by the handout.  I ended up having an error that took an hour of time and a fresh pair of eyes to find, but in the end, my solution worked, and I had a still-not-yet-proven-optimal solution for four stools. This was followed by coding the bonus, which took a lot less long than I thought.  Finally, I submitted Assignment 1 to MarkUs for the final time on February twelfth.

Labs this week flew by faster than I can say.  My partner and I finished within an hour and I do think I am improving in terms of my familiarity with recursion and my abilities to use it correctly.

Class this week was regarding trees. I'm quite excited about this, since graph theory is one of my mathematical favourites.  I'm not sure that my experience with König's lemma and Aronszajn trees will really help me in this class, but I look forward to this coming chapter of CSC148.  On the other hand, I feel slightly unprepared for the midterm, seeing as I haven't gotten any information regarding its contents, but I'm hoping that more information will come up during this week so that I will have time to fully ready myself.

Week 5: Assignment 1 and More Recursion!

During the past week, I've learnt a great deal on programming recursion!  I found it quite fluid and intuitive and I think I have math to thank for that.  The labs especially I felt were constructive, but not difficult and that the examples we went through during those two hours really solidified my understanding.  As usual, the posted course materials provided excellent examples that were also very useful.  If you want to see a nice explanation of a great example of recursion, check out this slog post: http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html!

The rest of my focus this week, has been mainly directed towards assignment 1 and all it's glory.  I remember in the fifth grade, I had a computer game and one of the mini-games within that game was exactly the Towers of Hanoi but with large wooden crates instead of cheeses.  I've also have a friend who had been to a math colloquium regarding the open problem of the optimization of the fourth peg, and who discussed the presentation with me.  I found it was a lot of fun to think about this familiar topic.  I am near completion for this assignment and I think I'm making good progress.

I would like to mention a few of my difficulties with this assignment.  The first being that at the beginning, the instructions felt quite random.  Upon seeing the TOAHModel.py file presented, I was confused as to what I had to write and what was written for me.  It felt like the instructions were presented in a jumble that I had to slowly sort through and that the corrections appearing via email and piazza were difficult to keep track of.  After many errors and much rereading and rewriting, I now have a working TOAHModel.py file as well as a well working ConsoleController.py file.  I'm quite pleased with my progress this week and I look forward to completing this assignment.  All this being said, I am now desperately craving a nice Gruyère.

Week 4: Inheritance, Exceptions, and Recursion

The vast majority of struggles I have in CS are to do with syntax. I have enough reasoning to figure out exactly what my program needs to do and exactly how it can do that, however, I just don't know how to say it with the correct programming grammar.  For this reason, I had some minute struggles with this past week's labs and exercises.  

At first during the exercise, I learned that I had no idea how to write exceptions.  This caused a flurry of rereading and looking through class materials, as well as a brief scan of other student's questions posted to piazza until I understood that the word I was looking was "raise".  Then my program was fine, except that I misread the instructions and programmed the error to catch odd numbers instead of even numbers.  Luckily the automated report system can catch whenever I make such an error; I really can appreciate how helpful it is.  Other than that, the only thing I had to take time to get used to is the new formatting for the code.  We had a specific way of writing the docstring in CSC108 that I had to adjust slightly for CSC148.  But I do think I am now familiar with it and have made a successful transition.

During the lab this week, we switched partners and I got to work with a new student.  Things went quite well, and I learned a great deal about unittest and inheritance, especially the syntax (!!!) that is required when writing code involving inheritance.  All in all things went well with the lab.  I think that the exercises and labs are excellent teaching tools because I have learned the most through those experiences, since I actually have to think and immerse myself in the language of python when I am actually writing  program.  That, at least for me, has been a very effective way to learn.  Now, I'm just looking forward to the somewhat daunting task of completing the assignment, and with that I am signing off for this week.

Week 3: Object Oriented Programming

Object oriented programming sounds like a daunting piece of terminology and for the longest time I wasn't even sure what it meant.  I suppose had I paid more attention in my Wednesday evening class, this would have been clear to me.  However, since I was used to CSC108's flipped classroom setting meant that it took me some time to adapt to this new format, despite the fact that all of my other courses are and have been not flipped.  That being said, I think I finally understand the definition thanks to a combination of posted course materials, Wikipedia, and a friend who knows more about computer science than I do.  Now that I know what it means, it's hard to see why I didn't understand before considering how intuitive the words are.  Object oriented programming is literally what it sounds like.  I guess the confusion arose from the fact that I have been learning object oriented programming without really registering in my mind that this was its name, and thus when the terminology was actually introduced, I assumed it meant something new.  That being said, I am certain I still have plenty of new things to learn about Python.

I am feeling comfortable writing new classes, and I am also feeling comfortable with the idea of Queues and Stacks and their respective methods.  All the material I've seen thus far in CSC148 I can logically understand, and the formatting is something I've already seen, as it was taught in CSC108.

So basically, other than a not so epic struggle to figure out what "object oriented programming" actually refers to, I haven't had many problems in the course thus far; the exercise went well, as did the labs.  I am struggling with the first SLOG entry but it will soon be done.  I expect the SLOGs will go better once I have better understanding of what they need to include as well as how they should be formatted.  As such, reading and comparing to other SLOGs once they are published should help.