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?
Thursday, 27 March 2014
Saturday, 1 March 2014
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.
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.
Subscribe to:
Posts (Atom)