Sorting Algorithms

       Now it is time to sort the sorting algorithms by which one has the best runtime in their worst case! But, which sorting algorithm will we use to sort the sorting algorithms?

       Alright, all joking aside, algorithm efficiency is an essential part of the basics of computer science. Algorithm is simply a fancy word for a series of steps to solving what seems to be a complex problem. Looking at complex problems, we know there are numerous ways to approach it.
       Let's take a look at the current gaming craze '2048'. You have a 4x4 grid, and you start off with 2 tiles of either two '2's or one '2' and one '4'.You can move them in 4 directions (up, down, left, right).  Moving two of the same number tiles onto one another adds them up. As the game progresses, more tiles of value '2' and '4' appear randomly. We have to add all those tiles up until we reach a tile that has a value of '2048'. One strategy is to randomly move the pieces around and hope they eventually add up to the 2048 tile. Of course, we know this quickly leads one to get stuck an lose the game. So that is not a good strategy to follow. A better one is thinking about how to isolate the tiles with similar values so they can be added together easily. You can pick one of the corners to push all the tiles towards, and you will see that it adds up to higher powers of 2 much faster than randomly moving the pieces around in the center.
      This is the gist of algorithm efficiency. We just have to figure out what kind of algorithm uses simple moves but solves a complex problem much faster. In class we were given some examples of sorting algorithms. There are ones that check through the entire list and swap items that are out of order, like selection or insertion sort.  Other sorting algorithms which continually split the list into smaller halves until a certain point and then they sort the smaller lists like merge sort and quick sort. The latter are much more efficient because even though both break down the problem into simpler steps, the former sorting algorithms always go through much of the list with each step, and the latter only goes through sections with each step, which is much faster.

       The important part is to remember that not all simple steps are equal, some are much better for certain situations.  Algorithms are then, in essence life lessons. We should all strive to do things the easier way instead of the hard way! What could possibly go wrong?

Week 7: Recursion is Recursion is Recursion is Base Case

        Recursion and mathematical induction are closely related. It was so obvious that I cannot believe I didn't see it before. Both of them require you to find the 'base case', the simplest problem that can be solved, first. After that, you find the more complex problems can simply be broken up into simpler problems that can be solved using the base case. Also, once we know how to figure out the previous case (in induction, we assume that to be the case with k), then the next case's answer is the previous case's answer plus some version of k+1. This connection helped me understand proof by induction in my calculus class.

        The concept of recursion is easy to understand for me, but interpreting it into code is another story. Usually, the recursive code we work with is not very long and contains a few list comprehensions. I am not that used to using them yet, so it can be tricky to figure out exactly what kind of comprehensions I need for the statement to make sense. Usually the code ends up too complicated. The numerous brackets do not aid in relieving me of my confusion either. One approach that I found really useful was to write recursive code "the long way", as in using if statements and for loops that take up quite a few lines. I do that first and test to see if the program works, and then I try to translate that into the shorter version that we are shown in examples in lecture, and then see if it works the same as before. This method seems to have improved my ability to analyze and write recursive functions for assignment 2. However, I think there are some instances when I do have to write a recursive function "the long way". A part of assignment 1 required us to write a few recursive functions that needed more than one line of recursive code.

Update on what I've learned

       Over the last two weeks, after some more recursion tracing and writing recursive functions, I understand this fundamental concept. I'm glad that I learned it just in time for the first assignment since a big part of it does hinge on recursion. The reasoning behind this concept is similar to certain methods of integration in calculus where a complex function to be integrated can be simplified by substituting u in some parts of the function and du into others. Solving for u instead of the original becomes much easier. Sometimes more than one substitution is required, so this can be seen as a recursive solution. So now I know that thinking recursively is not just key to learning computer science, but many important mathematical concepts as well.

      Something else that I also understand better is how to make short but comprehensive comments on my code. I am one of those people who enjoy explaining things at length even when there is no need to. Computer code is really just instructions for the computer to follow, so thinking about it like that, the comments are akin to what those instructions roughly translate to in English. This way I can get myself into the mindset for writing instructions instead of rambling on about the intricacies of life itself when commenting on computer code.

Week 3 SLOG: Object-Oriented Programming

As one of the students that had very little experience with computer science problems before last September, I find that I am getting the hang of object-oriented programming. In fact, using Python to write a simple function or class is becoming quite enjoyable. I think structuring a programming language so that concepts can be represented as "objects" or "classes" with certain attributes is a clear way for beginners to understand what is happening when information is processed by a program. The attributes tell us what it is capable of and what its limitations are. Methods are some basic actions you can perform with that object. This makes the objects in a program very similar to objects in real life. For example, an object in real life can be an atom. We know atoms consist of protons, neutrons and electrons. The different numbers of those sub-atomic particles that different chemical elements contain are like 'parameters' for their atoms. How different atoms interact with one another would be their 'methods'.

By using real world analogs, difficult concepts in computer science become less abstract.   This was especially helpful when we were creating the class Queue in tutorial on Tuesday. The name given to that class, "queue", implies the data structure works just like one. We can visualize a queue of people where everyone enters at the "back" of a lineup and exits from the "front". Once the person in front gets out, everyone's place in line shifts forward. This is analogous to the indices of items in a queue shifting down when the first item has been dequeued. The shift in indices was the reason why a Queue takes longer to enqueue/dequeue large numbers of items than a Stack can push/pop. I still have difficulty using proper computer science terminology so I will have to work on understanding object-oriented programming on its own terms and not in relation to something else. 

One thing I don't fully grasp are exceptions. I know that it is an object created in runtime errors, and I believe I can implement an exception in an acceptable way (as in it probably will not crash the computer). However I realize I cannot come up with a good explanation for exceptions which means there is a lot I do not understand about it. If I practice writing code with exceptions in it, or ask other students, the TAs, or my professor, I will gain a better understanding of exceptions and use them properly.