An algorithm for algorithms

Although of unparalleled importance to performance, algorithms, a workable-and-ideally-efficient procedure for solving a problem, can be difficult to develop. And, in practice, your problem will likely look distinct when compared to common examples that you learn in a first algorithms course, which can leave you feeling pretty helpless. Instead of trying to come up with the algorithm all at once, your best approach might be to go bottom-up by first considering your problem’s properties and several common algorithmic techniques.

Consider what the data of a solution consists of and the metric for determining if a given solution is correct. The naive approach, brute force, is to just guess all possible solutions until finding one that works. For some problems, there is no better approach. Although some may criticize taking such a low-level perspective, it first forces you to both better understand and formalize the problem.

Next, try to solve several small instances of the problem by hand and try to learn something about solutions. If you find yourself always making the same seemingly obvious decision, like always picking the largest valued item when trying to maximize profit given only the ability to choose one item, you may have a problem admissible to a greedy algorithm—an algorithm which makes a rather simple decision every step leading to the correct answer.

If you are given the solution to a subset of inputs, see if that allows you a way to solve the problem. If it does, it might be possible to break up your problem until you have the smallest subunit of your problem and repeatedly apply the “joining” logic between equally sized subunits, the divide-and-conquer technique. An example for finding the largest value would be by repeatedly considering the largest value in the left and right half of your list until reaching only lists of two elements, returning the maximum value between them and then doing the same for all formed left and right sublists.

Dynamic programming’s big idea is to save the result of a select number of prior, heavily-repeated computations to increase efficiency and speed. It also has a focus on subproblems; however, its subproblems are usually the result of some observation, or pattern, when solving the problem. For example, in the longest increasing subsequence problem, you are asked to find the sequence with greatest length using the elements within a given sequence. Trivially, you know that such a subsequence must have a last element at some position. You can, then, define the subproblem of the length of the longest subsequence found which ends at position i using only the elements before or at position i. These subproblems can be extended into a full solution through taking the maximum of all longest subsequences ending at specific indices, giving credence to its utility as a subproblem. When thinking of how to compute the maximum length subsequence ending at position i given all positions prior, you know that it must either extend an existing maximum length subsequence or form a new one. You then should take the maximum length found of all prior positions, for which the value at position i is strictly greater, and add one to it because including the current position would increase the maximum length by the single new element being added.

Another approach is to attempt to graphically represent your inputs either through their relationship to each other or to possible outputs. If your problem corresponds to some property of the graph or a type of search within it—attempting to make a graphical algorithm—most likely based on existing graphical algorithm ones, might do the trick. For example, if you were trying to find the maximum number of filled positions in a job given the application’s capacity to fulfill the requirements for each job, you could make a graph of two disjoint groups, defining one to be applicants and another positions. Then, you would link the members of each grouping only if that particular person can fill that position and recognize that the problem is “maximizing” flow from the applicant to the job groups using the available connections.

You can also try several “brute-force”-like solutions. If you can express the problem as a system of mathematical constraints on the output solution such as maximizing profit of a business giving the estimated profit and demand of possible products, you can probably apply an already existing mathematical optimization algorithm. If such a technique is not possible, you could instead try all possibilities, biasing towards those that “seem” promising. The former can be done through keeping a log of the best solution or partial solution found so far and then modifying/extending the solution slightly to see if another better one can be found, called an evolutionary algorithm approach. If, when trying the problem, you see a particular pattern of “good” things to try, you could bias the search towards these values first — a heuristic approach. During the search, however, if you are able to say that a particular partial solution cannot be extended to a full solution like when facing an invalid Sudoku board, you could apply backtracking. Backtracking basically stops whenever realizing it made a mistake and, instead of going forward, it reverts its decision and moves to the next possibility.

As heuristics can be difficult to develop and sometimes a problem is too difficult to formulate, learning algorithms such as neural networks can be used when examples of correct output and input are given which encourages the computer in a way to learn its own heuristics. Or, if approximation of the solution or having a probability of success is acceptable, the more general classes of approximate and probabilistic algorithms become available.

Even with these suggestions, you might find yourself stuck. In that case, beyond trying a few more examples and looking at some other similar problems, it may be best to rest on it for a few hours or days. Most of the time, to find the algorithm, it takes adopting a new perspective which is very hard to do in a single sitting. If you want to become practiced in this type of thinking, I would encourage you to either try out some of RPI’s algorithm class offerings, attend programming competitions, or simply practice with online resources like GeeksForGeeks, Leetcode, or HackerRank, but, as with anything, practice makes perfect.