Week #11: Sorting

When a closet is messy or disorganized, even if you know those shoes that go perfectly with your new dress are in it, often it doesn't feel worth it to sift through the piles of clothes that don't fit anymore and winter coats you won't need for months to find them, so you end up wearing those boring black ballet flats out of convenience.

Sorting in computer science is important for this same reason. Much like it does not matter how big your closet is if you can never find anything, it does not matter how much data a computer or program can store if it takes an unreasonable amount of time to access and perform actions on or with that data.

Overtime a number of effective sorting algorithms have been developed, but some, as we will see, are less time consuming and expensive.

Here are a few of the most well-known sorting algorithms:

Bubble Sort: This algorithm makes passes through an array, comparing adjacent items, and swapping those that are not in the right order. If someone was going through there closet and wanted their winter coats on the left, fall jackets in the centre and spring cardigans on the right, and they saw a fall jacket on the far left, if they used bubblesort they would look at the item directly next to it. If they saw a winter coat they would swap that with fall jacket, on the other hand if they saw a spring cardigan they would not swap the two and would move on to comparing the spring cardigan to every item in the closet until it was in its proper place. They would then repeat the process until the closet is sorted.

Obviously this is not an efficient way to sort a list or a closet. Bubblesort exchanges items with other items before we even know where that item is supposed to go. This leads to moving items from incorrect positions to incorrect positions, which is expensive and time consuming. In its worst case bubble sort takes O(n**2), but it's worth noting that on a sorted list bubble sort can stop early because if there are no exchanges during a pass the list is sorted.


Selection Sort: This algorithm is similar to bubble sort, but it does not make unnecessary swaps it avoids doing so by first looking for the largest value, in a list and then swapping it into its proper place.

For example, if you were organizing shoes by their heal height, you would begin by looking for the really tall five inch heals and moving those into there place, then doing the same with the three inch platforms, then the nikes, then finally the ballet flats.

Selection sort is still O(n**2) because it makes as many comparisons and bubblesort, but because it avoids unnecessary exchanges and it does tend to execute more quickly.


Insertion Sort: Insertion sort is a bit like if you decided to just start fresh and move everything to a new closet entirely. It treats the first portion of the list as a sorted sublist, and goes through each item, adding it to its proper place in this sublist, until the sublist becomes the list.

Insertion sort is still O(n**2), given that the number of comparisons in its worst case would be similar to that of bubble-sort and insertion sort. However, on a sorted list, only one comparison would be made per pass.


Merge Sort: This algorithm really speeds things up. Using recursion merge-sort divides and conquers' the a list. Essentially merge-sort splits a list in half sorts each half using merge sort (i.e. merging them together) then 'merges' them together again. It is basically like if you had as many friends willing to help you organize your closet as you do items in your closet.

Merge sort is O(nlogn) or 'linearithmic', making it much quicker then the previous algorithms, but it also requires much more space as it needs to store the 'half lists' separately.


Quick Sort: This algorithm is similar to merge sort, but it avoids using the excess storage by using a 'pivot value' and moving items to the side of the pivot value which they belong, instead of splitting the list in half.

If the pivot value is always in the middle of the list, then it will be O(nlogn) like merge sort, but without the excess storage. In it's worst case though, the algorithm will be O(n**2), making it as inefficient as something like bubble sort.

Week #8: Assignment 2 Stage 1

     This week I completed the first portion from Assignment 2. Although, it felt substantially less frustrating than past computer science assignments, it brought with it new, less familiar difficulties. The assignment focused primarily on designing a collection of classes to represent regular expression trees. Due to the fact that the entire purpose of the assignment was for us to design our own representation of the regular expression trees, the instructions were quite vague.

     Therefore, the assignment required much more higher level, abstract thinking, and less debugging and nitpicking. Initially I struggled in choosing whether or not to include a parameter that allowed the client to choose the root for the regular expression in the specialized classes. For example, an 'asterisk regex' will always have an asterisk as it's root, so why not just omit that parameter entirely? However,  I ultimately decided to include it because it seemed easier to maintain, in case of an update or change. Whereas, if I had hard-coded the value it might create unforeseen difficulties later on.

     I also focused much more on style, doc-strings, and creating clearer error messages in this assignment. In previous assignments, I was so focused on getting the program to work the way I wanted it to that I often slacked off in that arena, but this time, given the simplicity of the task itself, it felt crucial that clients of my code understood exactly what it did and why, and that everything was clear.

     Overall, I really enjoyed this assignment because it gave me an opportunity to work on certain skills needed to succeed in computer science that I have not been practicing as much as I should be.

Week #7: Recursion

     Recursion was not an entirely new concept to me, as I entered into CSC148. I had dealt with smaller recursive functions on my own time and it seemed simple enough. However, as we started to write and trace more complicated examples in lecture, and began to use recursion to solve problems I never would have considered using it for before, I gained a much deeper understanding of the topic.

     A recursive function is -- at its most basic definition -- a function that calls itself. To expand on that slightly, it is a function that calls itself until it reaches a 'base case', which is the solution to the least complex version of the problem the functions solves. If there was no base case a function would hypothetically run forever, or at the very least raise an ugly error message.

     It is very important to not over-think recursion, whether you are tracing someone else's code or writing a recursive function yourself. I was very confused by the Tower of Hanoi code, initially, because I could not wrap my head around how a complex problem with many steps could be broken down to just moving a one cheese from the source to the destination. However, when I went back and read the steps I realized the code represented the steps that needed to be taken almost word for word.

     The concept of a function calling itself can seem very unsettling at first glance. We cannot use a variable name that has not been defined yet so it seems counterintuitive and circular to define a function in terms of itself. However, just like we can define x = x + 1, as long as we've already defined x to be a constant value, we can also define a function in terms of itself as long as we a have a base case.

     If we view a function as a general set of instructions rather then a unique application of these instructions recursion seems like an obvious solution. For example, while all the mail in Toronto could be delivered by a single mail carrier, who was the only one to receive instructions/training on how to do his/her job, it is much more efficient to provide many mail carriers with the same training/instructions and have them each deliver mail in a smaller subsection of Toronto.

     A recursive function does the same thing. It breaks up a function into many smaller versions of the same problem that can be solved in the same way. It then solves these smaller problems in order to solve the larger problem.

      A tree then, is not only a very useful abstract data type, it is also in many ways a physical representation of recursion. Each tree 'branches out' into many subtrees until it reaches the smallest tree possible: the leaf. Although, I have not learned much about trees yet, I look forward to applying my knowledge about recursion to our next assignment on trees, and hopefully understanding both concepts on an even deeper level.

Week #6: Finishing Assignment 1

At the beginning of this week, I had been feeling very good about how my assignment was going. I only had the last two steps left to complete, and felt strongly that I was on the right track.

Unfortunately, Step 5 -- finding the recursive solution to the cheese problem with 4 stools -- proved to be substantially more difficult than I was expecting. I understood out how I should move the cheeses once I new the split 'i', but finding that 'i' seemed impossible. I spent all afternoon on Wednesday testing out different potential solutions, but even when I could find the minimum number of moves, I could not seem to extract the 'i' from function, given its recursive nature.

I expected to spend all Thursday at the library as well, and crossed my fingers that I would find a solution. However, the next morning, after detaching from the problem, a solution occurred to me much more quickly then expected. I could use nested functions, given that I needed the index from the function that found the minimum moves, but could not change the return statement because that would lead to issues during recursive calls.

I learned this week that sometimes staring at a problem for several hours is not the best way to solve it. Often it is better to detach from the problem temporarily, and come back to it later with a fresh pair of eyes.

Week #5: Understanding Namespaces and an Assignment 1 Update

     This week in lecture the aspect I found to be most confusing was not recursion, it was the namespace example we were shown on Wednesday. At first I thought I understood it clearly because the theory made sense to me. Much like math equations have an order of operations (BEDMAS), names in python are given a certain level of priority based on where they are defined in python code. A python interpreter first searches for a given name locally (within the innermost function), and works its way outward through the nonlocal names, and global names, until it finally reaches the built-in names. However, I felt lost once we began to go through the following example:

          # local, nonlocal, global scope

def scope_test():
    def do_local(): # nested function --- only available inside scope_test()
        spam = "local spam"
    def do_nonlocal():
        nonlocal spam
        spam = "nonlocal spam"
    def do_global():
        global spam
        spam = "global spam"
    spam = "test spam"
    do_local()
    print("After local assignment:", spam)
    do_nonlocal()
    print("After nonlocal assignment:", spam)
    do_global()
    print("After global assignment:", spam)  

scope_test() 

print("In global scope:", spam)

     Everything seemed murky, and I didn't quite understand where certain results were coming from, or why certain results were being printed. I remembered the last time I felt this way was about the exceptions example we were shown in class. What had helped me the most in that situation was copying the example into Wing, and actually working with it myself. I decided to do that with this code as well, an it helped me immensely. For example, although it may have confused me in class, when I tried it myself I understood that  'After global assignment: test spam', was being printed because of the order of priority I had theoretically understood before hand. It was also interesting to note that 'nonlocal spam' overrode 'test spam'.

     As far as my progress on Assignment 1, I have finished implementing the actual game, but now I must complete the recursive element. That is, I must solve Anne Hoy's moving problem as efficiently as possible. I think, (as Sandra mentioned in her SLOG: http://sandracsc148slog.blogspot.ca/2014/02/week-5.html) I am going to find the lesson on the recursive solution to the problem using 3 pegs that we discussed in class, very helpful when finishing this assignment.

Week #4: Tracing Recursion, Using Unittest, and Starting Assignment #1

     This week I found the material we covered in lecture to be substantially easier to follow. Generally speaking recursive functions are not something I struggle with -- whether I am writing them or tracing them.

     That being said, I found the lab this week substantially more difficult. Although, my partner and I implemented the required classes promptly, neither of us had had much practice using unittest to test our programs. We had to look up unittest in the Python 3.3.3 documentation and carefully go through the example posted, before we attempted to apply it to our specific program. While we spent more time debugging the syntax errors and spelling mistakes in our unittest modules than Motorized and its subclasses, we did eventually get all of the modules working.

     As far as assignment one goes, I have now completed the module headers for TOAHModel.py, and have begun to implement them. I was not entirely sure how to represent the cheeses on the stools at first, as I could not tell whether the stool counted as a 'cheese' or not. However, by searching through the course forum, I found that another student had had the same question, and an answer had been posted.

     Overall, this week I have learned that when I find myself stuck there are plenty of online resources I can turn to to get myself 'unstuck'.

Week #3: Object-Oriented Programming

            During the first two weeks of class I was not concerned about delving into object-oriented programming. I believed that object-oriented programming was essentially the same as the programming I had done in 108, except it sorted the functions into classes to improve organization. Any new concepts that were introduced – such as ‘property’, list comprehensions, and even recursion – were concepts that I felt I was able to understand completely just by thinking through the examples (i.e. sum_list) that we were shown in lecture and working through the lab exercise.

            This week, however, – whether it was due to the material itself, or the fact that I was sick with a cold – I had trouble paying attention in class and found myself substantially more overwhelmed by the material. I followed along well enough when it came to inheritance and composition, but when that was combined with the example of the code on exceptions I was lost. I also had no clue how the str and repr method were related.

            To resolve this, I began by reading the readings for this week. The reading on Inheritance vs. Composition really clarified for me how class hierarchy works, and how different methods can take priority based on when and how they are called (i.e. if the child class has a method that has the same name as a parent class the child classes method will have priority unless you alter this by using something like the super function). Even though, we went over this topic in lecture, sitting down and having a chance to go through the material at my own pace made a difference.

            There was not a lot of information in the readings on __str__ vs __repr__, so I looked up some tutorials on YouTube and questions that were asked in forums. These gave me a vague understanding of their differences. __repr___ is a representation of an object intended for the developer whereas, __str__ is a readable printable representation of the object. I still did not entirely understood how the worked though.

            I decided to copy and paste some of the examples I found into Wing and try them out myself. I then altered them based on the questions I had about the material. From this I learned that __repr__ is a superclass to __str__. I also learned that if you try to print an object that is a tuple or list, python will use the __repr__ representation rather than __str___, unless you specifically call the __str__ method on each item. However, for non-iterables, it prints the object’s __str__ representation.

            Testing out the code in this way worked so well for understanding each of those methods that I decided to use a similar strategy in order to understand the exception code I struggled with in lecture. Unsurprisingly, commenting out certain portions myself and running the code on my computer really clarified both inheritance and exceptions for me.

            This week I learned that object-oriented programming is a lot more than writing functions as I always had, and sticking them in something called a class. It is about directly grouping your data with the methods that will be performed on/with it. It is also, about clarity and organization not only for you, but also for other programmers who may want to use your code or compose it with their own. Mostly, it stems from the idea that programs are not laundry lists of different functions. They are like webs. Preferably organized webs,