Algorithms are ubiquitous, and you shouldn’t need a Computer Science degree to learn them. Set up a problem in the right way, and you can solve them trivially, or at least know that you have to live with an approximation. They don’t have to stay under-appreciated until you need them: here are five basic algorithms that you must know, with some real-world applications. Try to learn the underlying structure — you’ll find that they are recurring problems! (Only provided brief overview - if you want to learn more about them, use the links!)
Sorting
This is the most fundamental and essential thing in algorithms, and often the first thing you do to create structure and order out of chaos. This means about the same in English as it does in Math. There are a bunch of crazy sorting algorithms out there: Quick sort is the one that might be the most well-known, while merge sort is useful in a few instances. Introspective sort might be the most important one of the bunch — its fancy name is a cover for using different sorting algorithms depending on different steps of the way, employing the strengths, while sidestepping the worst-case scenarios. It’s a great idea that can apply in other situations — you don’t need to find an algorithm that is the best for everything, use the best parts of each algorithm for each case!
Real World Applications — Sorting is everywhere you want to create structure for quick retrieval. Sort your bookshelf alphabetically so you can find things easier. Sort a deck of cards so you can rig the deck. Sort your friends and enemies.
Steps of Binary Search
Binary search
The classic example of Divide and Conquer. Incrementally make your problem a smaller one, until it is trivial. What it exploits is an inherent order, usually created by sorting, that allows you make observation about the answer on every query.
Know the game 20 questions? You get 20 questions to guess a word. Well, since the English Dictionary has about 500,000 words, the simple way to cheat is to cut it half way every time.
It’s boring, but you’ll win every time:
Does your word come before the word “marry”? Yes Does your word come before the word “gerrymander”?
You get the idea.
Binary search is quick: You can go through a dictionary with 2^64 entries in just 64 questions. 2^64 ~ 1.8 * 10^19, or a very big number.
Real World Applications — According to folklore, Professor Skiena would demonstrate binary search by asking for a name, and then looking it up in the phonebook by checking the middle of the book, does a comparison, and literally tear out half the book and throw it in the trash. You can probably come up with a less dramatic example.
Hashing
The legendary Udi Manber said that the three most important algorithms at Yahoo are “hashing, hashing, and hashing”.
Imagine you have a closet full of shirts, and it’s time consuming to find a particular shirt - you might have to go through all of them. What can you do?
Hash it. Take every shirt, one at a time, and put it in a different drawer depending on the color of the shirt. Label the drawer. Whenever you want a shirt of a particular color, just open the drawer with the corresponding color. That’s hashing in a nutshell.
Of course, you might (and likely) have more than one shirts of a given color. This is a hash collision. Dealing with hash collisions in a “perfect” way is mostly in the realm of research papers, but know that they exist.
No one ever got fired for using a hash table before!
This is conceptually easy, and many tend to use it as a black box without giving it much thought. Real hashing is hard, but using a hash table is relatively simple.
Real Life Application — You can pretty much hash anything, if the ordering is not important. You can then quickly retrieve items.
I have a box of Xbox 360 games, and a box with a Wii game. If I want a Wii game, I can easily reach for it in the box. If I want an Xbox 360 game, I can reach for it in that box. However, if I have many Xbox 360 games, and want a particular one, I would need a better method — perhaps sorting it by title within the box, or a few smaller boxes within the box, hashing on the game type: adventure, action, etc.
Dynamic Programming
Also sometimes referred to as memoization. (No, not memorization.) Think of this as caching- save the results so that you don’t have to do the work again! Dynamic Programming refers to finding some structure within the problem to abuse this cache. Be lazy, reuse results!
One of the canonical examples of dynamic programming is the Fibonacci sequence. I will ignore it here, and introduce the “Coin Change” problem instead.
You’re a cashier at a store. A customer pays for something, expecting change. You want to give the exact change back to the customer, while using the fewest number of coins. You can restructure the problem in terms of its subproblems:
What is the fewest number of coins to make change for N cents?
Well, that’s just the fewest number of coins to make change for N - 1 cents plus one coin, a penny
or
the fewest number of coins to make change for N - 5 cents plus one coin, a nickel
or
the fewest number of coins to make change for N - 10 cents plus one coin, a dime
or
the fewest number of coins to make change for N - 25 cents plus one coin, a quarter.
Notice a pattern? You answer a question with a question - a smaller, easier question. Another pattern? You might ask the same question over and over again. For example, you might get to N - 5 by 5 pennies, or a nickel. In fact, this grows rather quickly and is a literal exponential function. How to solve this? Remember the result, and you won’t have to do the work over and over again!
Note that for most modern currencies, the greedy algorithm works for this problem - simply take the largest coin that is smaller than the requested amount, subtract, and repeat.
Real Life Application — Want to know what is the probability of getting X heads out of N coin flips? Well, that’s just the probability of getting X - 1 heads out of N - 1 flips (if I flipped heads) and X heads out of the remaining N - 1 flips (if I flipped tails). Take the weighted (50% for a fair coin) average!
Image via Wikipedia
Search Algorithms
I want to put basic graph theory in general, but search algorithms are great places to start. The fundamental ones: Depth-First Search (DFS) and Breadth-First Search (BFS). Understanding these might lead you to more exotic sounding searching algorithms, like A*, but start with these basics. Many things can be modeled as a graph, and these are simple algorithms to play with by yourself. DFS generally worms its way through paths, while BFS branches out. Each algorithm has its own strengths and weakness, be sure to explore them!
Real Life Application — You need to know if you can get from point A to point B. Start driving from A, and mark off areas you’ve already been. If you reach a dead-end, turn around and come back until you find another road that leads to a place you haven’t been. It might take awhile, but eventually you’ll either run out of roads, or you’ll be at point B!
When it comes to Computer Science, in contrast with Software Engineering, there will always be people who will maintain that it does not come up in the “real world”. It might be true the majority of the time, but you can’t solve problems elegantly if you can’t solve problems at all. Just knowing that certain problems cannot be done in polynomial time frees you from searching or figuring out an exact solution. It’s about expanding your toolbox for whatever work or life might throw at you. They might not come up often, but when they do, you’ll be glad you know where to find the answer!
