Algorithms and Problems

Nick Teal
4 min readMar 21, 2018

An algorithm, simply put, is a set of instructions. Often it carries an implication for mathematics or computer science. The purpose, much like a recipe in cooking or the procedure of a science experiment, is to provide a method to continually achieve a desired outcome. They typically do so efficiently, and allow for you to share or borrow methods with or from others in a succinct way, or hold on to for your own use without having to ‘re-invent to wheel’.

While any set of instructions (again, usually referring to mathematics or computer science) may correctly be called an algorithm, there are several categories of algorithms that are popular. These can be classified in different ways, often by implementation or by methodology. Consider recursive algorithms vs divide and conquer algorithms. Recursion in this context refers to a class of functions or algorithms that ‘calls’ itself until it hits some base case. Divide and conquer algorithms refer to a class of algorithms that continuously divide the problem set until a solution is found. Often times recursive algorithms do divide and conquer, but not necessarily. In this example recursive algorithms are labeled by their implementation while divide and conquer algorithms are labeled by the way they solve the problem.

Besides recursive and divide and conquer algorithms, some other major algorithms include optimization algorithms like dynamic programming algorithms or greedy algorithms and algorithms that work specifically for trees or graphs. While some problems can be solved in different ways, there is often an optimal type of solution. For example, problems that can be broken down into sub problems and a final solution made from the solution of those sub problems, could likely be solved recursively. That being said, if those sub problems rely on each other, they could also be solved using dynamic programming, which is similar to recursive algorithms, but also memoize or cache solutions for faster performance. That being said, if this particular solution could actually be found by combining solutions to sub problems, but only in specific ways, a greedy approach (which is to build the solution of the next problem off the solution of the previous problem, but only if it leads towards the total solution) could be used and might be the fastest choice.

Before jumping into a problem, take a second to make a plan. In fact, you should spend some time making sure you are solving a problem that can be solved (in the time you have). Problems are often lumped into classes of polynomial, non-deterministic polynomial, and undecidable. There are more classes than these three, but these cover a lot of problems we typically experience. Polynomial problems are decision problems that can be solved in polynomial time. Here decision problems refer to problems that can be treated as ‘yes or no’ problems based on the input, and polynomial time refers the time complexity of solving that problem. To be a non-deterministic polynomial, a problem must be a decision problem and be testable in polynomial time. That is, given a possible solution, the algorithm must be able to decide if that solution does in fact solve the problem, or not, in polynomial time. Undecidable problems are a different class of problem, and cannot always be solved by a single algorithm. After you’ve considered whether your current problem is solvable, decide which algorithm will best suit your needs. If there are more than one algorithm that will work (which there often is), decide which one to use based on how good a fit it is.

How “good” an algorithm fits is often decided by its efficiency, completeness, and or its eloquence, just depending on the specific need. These are often trade offs. For example, to completely solve a problem that is NP, it could take exponential time. That being said, there could be an optimization algorithm that returns a good approximation in polynomial time. Here the trade off is efficiency vs completeness. Other times an algorithm may be improved with high level computations, making it less eloquent. These are good tools to match against your needs for a specific algorithm.

This certainly does not cover all algorithms or problems, but gives you a good starting point. Use these ideas to start deciding which problems are good problems to tackle, and think analytically about which algorithm may be your best bet. Then do some more research to learn about more algorithms and problems, and specifics of applying them to grow even more in your understanding and experience with algorithms!

--

--