Classes of Algorithms

Algorithms can be a number of classes:  fighter, wizard, monk…

dice
Ok, that was bad.  I apologize.

My last post was about what algorithms are and why they should not automatically be feared.  As an extension to that, today I’m going to be talking about some of the different types, or classes, of algorithms.  Knowing more about the internals of a problem can lead to better understanding and discussion across the board. Most algorithms that you’ll come across in practice aren’t going to be as simple as to fit into any one of these categories, but understanding the pieces of them allows you to get a better grasp of the system as a whole.

When you’re looking at a problem as an engineer, a lawyer, or really anyone in any profession, it’s good to know a lot of strategies to get your end result.  This way you can always pick the one that’s best suited to the task at hand. Below are a number of categories of algorithms, a bit about each, and when they’re particularly well suited to solve your problem.

Brute Force Algorithms

Brute forcing is exactly what it sounds like.  It represents the second most illogical solution (the first and worst possible solution is mentioned at the end) of trying all possible combinations one by one until you find your solution.  Even for a task as easy as a three number lock with digits 0-9, this provides a thousand possible combinations. Think of a bot that plays chess. If it had to simulate every possible outcome of the current board state, it would take hours.  Because engineers only find pleasure in wasting energy crunching pointless amounts of numbers when they aren’t paying the power bill for the servers, this form of solution is relegated to CS 101 and other similar silly or impractical applications. The one nice thing about brute force solutions is they take almost no time to implement in code whereas fancier solutions will be faster but take longer to implement.

Divide and Conquer Algorithms

Now is when we start getting into the big leagues.  Divide and conquer algorithms are particularly well suited to problems that have a large amount of small operations happening.  In other words, you can take the entire work, break it down into a number of small pieces, perform the calculations / operations / etc, and then reassemble the pieces into a complete solution.  The easiest example of this requires no actual splitting and reassembling: cleaning a house by assigning each person one room. Many hands make light work, as they always say. (They also say what one engineer can do in a day, two engineers can do in a week, but that’s a different kind of problem.)  

These kinds of solutions usually come up in distributed computing when there’s a giant math problem to solve or when there’s a giant pool of information that needs to be searched. It’s very easy* to split up the pool of resources, assign one section per server, and then just merge the results once all of the servers have an answer.

*By very easy I mean that it took decades worth of engineering people-hours and billions of dollars to get right.  Citation: an inconspicuous and hardly visited web site called google.com

Greedy Algorithms

Greedy algorithms (or anything that uses a heuristic function) are some of my favorites due to how easy they are to code versus how accurate their results are.  If you couldn’t tell from the name, greedy algorithms will always choose the best solution or easiest path from where they are currently (even if it’s not the best solution in the long run!)  This comes into play when you’re traversing graphs or trying to load a backpack with stolen goods of various sizes.  Sometimes it takes a long time to figure out the most optimal path, so a pretty-good-looking-one will do just as well. These algorithms shine when there are massive nonlinear data sets where it gets computationally infeasible to find the absolute best.  

Dynamic Programming Algorithms

These are the most conceptually hard of all of the classes listed here.  The short of it is that they work backwards on a problem computing a bunch of easier to solve sub-problems by adding to a knowledge base piece by piece.  The Fibonacci series (read about it if you’re unfamiliar) is a good way to exemplify DP. To find the 5th Fibonacci number [noted f(5)], we must first find f(4) and f(3).  To find those, we need to find f(2), f(1), and f(0). When you expand that all, it looks like this:

f(5)  
= f(4) + f(3) 
= ( f(3) + f(2) ) + f(3) 
= … (going to save us all time and brain cells)
= ( ( ( f(1) + f(0) ) + f(1) ) + ( f(1) + f(0) ) ) + (( f(1) + f(0) ) + f(1) )

And this is a lot of work.  It’s much easier just to keep the solutions in memory so that the first time you see f(2), you do f(1) + f(0).  The next time, you already have the value so there’s no point in recomputing it. This type of algorithm takes clever implementation skills and sometimes has a bit of memory overhead, but it can produce really solid results for problems that would be way too hard any other way.  One classic example is the popular operation diff that finds the differences in letters between two bodies of text.

Random Shuffle (Bogosort)

As promised earlier, here’s the worst possible class of algorithms.  They’re so bad in fact, that they don’t even have a guarantee of completion.  They’re called the random algorithms because they shuffle the problem elements randomly and then check if the problem is solved.  This is exemplified by the infamous Bogosort which does just that. It takes a list of unsorted elements and randomly shuffles them until completion.  This just goes to show that no matter how dumb the idea is, someone has already thought of it and written an academic paper on it.

The pseudocode:

while not isInOrder(deck):
    shuffle(deck)

Glorious, isn’t it?

Lastly, I leave you with this: an amazing visualization (and audioization?  Is that a word?) of sorting algorithms. Watch it when you have time, it gets pretty hilarious.  (Watch out for the ol’ bogosort at the end! [5:18])

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s