Sorting

Back in high school, we had to sort things sometimes. Everyone used Bubble sort, because we didn't know any other way to go about sorting. I remember thinking about sorting one day, and could not for the life of me come up with some other way to sort. And then came the day we talked about sorting in this class, and my mind just went "oh."

Selection sort is the closest thing to bubble sort, and kind of works on the same principle. In Bubble sort, you compare each pair of values next to each other, and swap if necessary. In Selection sort, you find the minimum (or maximum, or whatever else you're looking for) of the whole array and swap it with the first value, then repeat for the whole list starting from the next index. Had I ever thought of a different way to sort, it would have most likely been Selection sort, due to the iterative nature of the sort. I'm pretty sure that I didn't know recursion at that point, which is why I would never have come up with these next sorts:

Quick sort and Merge sort. These completely revolutionized how I thought about sorting. Not just because they're recursive, but because they're actually very simple concepts. Quick sort: separate the array according to each element being less than or greater than the first element, then sort each new array, and put all the pieces together at the end. Merge sort: cut the array in half, sort each half, then put the halves together by picking the smallest element between the two, then the next smallest (or largest, then the next largest, etc), and so on. These are perfect examples of how to properly use recursion: break a problem down into smaller copies of the same problem, until each portion can be easily managed.

So we have all these sorts, which do we pick? We probably want the fastest one. How do we know which is the fastest? We have to test them. However, we can't just do a single test, we need to know how the performance of each algorithm scales with the size of the input to properly determine their efficiencies. This is because the runtimes of different algorithms may not stay proportional to each other. After testing in class, and in one of the labs, we determined that Quick and Merge greatly outperform Selection, and Selection greatly outperforms Bubble, at large array sizes. However, at smaller sizes, there was no clear victor in terms of speed. As well, there may be situations where you need to sort an almost-sorted array. In that case, sorts like Selection and Bubble see a large increase in speed, where Quick and Merge don't.

The moral of the story: built-in sort outperforms all of these =\

NoneTypes

Let's say we have a function do_something(item). The parameter item is a class that has an attribute called thing. When this function is called, it needs to perform an operation on item.thing so long as item is not None, and thing is a string. My first thoughts on how to do this were to check if item exists, then check if thing is an instance of a string, in that order. The first line of my code looked something like:

<the things needing done> if item.thing and isinstance(item.thing, str) else <don't do stuff>

My reasoning was something like: Well if item is not None, then it has a thing attribute, so if item.thing returns false then item must be None! Well...turns out this isn't the case, and this mistake cost me two whole marks on Test 2. If item is None, then trying to do anything with any attribute of item will throw an AttributeError, because NoneTypes have no attributes. In order for a bool(item.thing) call to return False, item.thing has to be explicitly initialized to None, or 0, or an empty string, etc. Looking back, this was such a stupid mistake, and it would've been fine if I had just had item instead of item.thing in the first check.

One thing I've noticed about the sample solutions for recursive functions is that they only ever check if the parameter itself exists, not any attributes of the parameter. For whatever reason I've been writing code that tries to avoid passing None as a parameter recursively, but also having to deal with the case that None is passed explicitly from outside the function. Had I noticed this earlier and incorporated it into my own code, the above mistake probably wouldn't have happened =\

Regular Expressions

Our second assignment was the first time I had dealt with regular expressions. As always, I was looking forward to working with some new concepts after I had read through the assignment handout. A regular expression (regex for short) is a series of characters that can be interpreted by an appropriate class into a set of rules. These rules are used to determine if a string belongs to the regex, or if it doesn't. Other than a fun programming exercise, I didn't really see any practical applications of this. Turns out that regexes can be very useful in aiding the interpretation of a string. If you need your program to read files, but treat different types of strings in different ways, comparing sections of your file to a list of regexes can help you classify them for proper handling. Another use of regexes might be in detecting cheat codes in games. Instead of having a "Cheats" menu option, which would lead to a screen where the user can input codes in a textbox of some kind, consider continuously scanning the user input during normal gameplay. If a series of inputs matches the general "cheat code" regex, then said inputs can be compared to a list of cheats, and the appropriate one activated.

As far as the assignment itself, I was kind of disappointed. After scrambling within the last few days to get through the first assignment, I gave myself plenty of time to work on this one. The thing is, this assignment was easy. Once you understand the concept of regexes, and the set of rules described in the handout, the actual coding was fairly simple. The rules for the various operators were practically written in pseudo-code, ready to be translated into Python syntax. I feel kinda bad saying that, because I know there were many people who struggled with this assignment, but this is just my opinion. It is not my intention to make anyone feel inferior (because you aren't), I just wanna write a blog post =\

QPython?

So I got bored and tried looking for a Python editor for my Android, and lo and behold there is one (and probably more, but this one seemed to be good enough). QPython is a free app available on the Play Store that includes the Python interpreter, a .py editor, and a Python console; along with various example scripts and supplementary libraries. Aside from the normal inconveniences from typing large amounts of text on a phone, the program seems to handle fine, performing without too much slowdown and not heating up the phone any more than it should (except on maximum recursion depth errors, but those speak for themselves). However, after playing around with it for a bit, I realized that i was using a Python 2 interpreter! A quick look on the Play Store revealed QPython 3, which additionally came with an interactive Python shell. Now, as long as I have my phone, I can never claim boredom again :P

OOP and Recursion

A writing assignment in a CS course! What is this? D:

Oh well, I guess it could be worse. Some of my friends are stressing out over essays, on top of their term tests. My cousins as well. All I need to do is write two measly paragraphs, so here goes!

Object-Oriented Programming is one of the major code structures. It is a natural way to structure programs, based on classifying components by similarity. It starts with one or more superclasses, foundations for the code that contain properties and methods used by many different parts. Each superclass then has subclasses, which each build upon their respective superclasses in unique ways, specializing for certain tasks. These subclasses may have subclasses of their own, which are even more specialized. Once all the classes have been defined, an instance of any class is created, called an object. Said object has all the properties and methods of the class it was instantiated from, as well as all the properties and methods of that class's superclasses. When another object of that class is initialized, it has all the same functionality as the first instance, but it is entirely separate. Think of a forest. One of the main superclasses for a forest would be a Tree. The Tree class has many different subclasses, one for each different type of Tree. Many, many instances of each type of Tree are created. All the Trees of one type share the same basic attributes, but each Tree is it's own Tree. This one has x amount of branches, that one y. This one is at location p, that one q. This code structure is an extremely useful tool for developers, as it is completely intuitive; and at it's core, simple.

Recursion is a bit of a more difficult concept to grasp (for trouble grasping recursion, see paragraph on recursion). It entails breaking a problem down into smaller copies of the same problem, which all have a common solution. To actually do this in code, you need to call the method that you are currently defining. What? Is this even possible? Do we have the technology? We do, in fact. But how can we call a method that isn't yet defined? By the time the code is run, you've most likely finished writing the recursive method. If written properly, you should have addressed all possible inputs and outputs for this method, so that it doesn't loop on itself forever. Let's go back to our example of the Tree class. Branches could be considered a recursive structure. The trunk is one big, vertical branch. It splits into many smaller branches, which split into more branches, and more, and more....until there's no more splitting, and each branch now has a leaf at the end. How does the tree know to stop splitting it's branches? The deepest level of this recursion is that there is no split, and a leaf is formed. The function that splits branches in the Tree class should be checking for the radius of the branch, and when it gets too small, stops looping recursively, and makes a leaf. When this happens, the method will continue at the last split, moving on to the next branch. As it goes along the branches and comes back, it will eventually get to every leaf on every branch. Methods like these are very powerful, and can do a lot with a small amount of code. However, sometimes they aren't necessary. For example, in the latest tutorial, one of the bonus exercises was to compare every integer element in a list, and return the number of times a larger integer is on the left of a smaller one. This is much easier to perform with nested for loops, which will compare every possible combination of integers only once. I couldn't even find where the recursion would go in that case, but I didn't have enough time to ask the TA. Oh well =\