Finding a new algorithm or solving a problem can be a daunting task because we don’t know where to start. What are the techniques that we can reuse to approach a problem? Can we create our algorithm to find algorithms!

Understand the problem

It sounds obvious, but the first thing is intimately understanding the problem or question. Start by listing the variables. Find the things you can change, and that influence the output.

• What are the constants and the invariants?
• What are the inputs, and what is their format (e.g. numbers, letters)?
• Are they discrete or continuous values?
• How are the inputs related to each other; are they independent variables?
• What is the output and its format?
• What are the constraints?

Examples and base cases

Now that you have a better understanding of the requirements, you can start finding general rules by studying examples. Draw a list of examples, starting with simple ones. When I have these inputs, I expect these outputs.

Many problems have a recurrence relation. One result depends on a previous result. Finding the base case is a good start. Take the famous Fibonacci example. You want to find an algorithm that outputs 21 for the input n equals 8. First, you list the most straightforward examples and the base cases.

n = 0, output 0, base case
n = 1, output 1, base case
n = 2, output 1
n = 3, output 2
n = 4, output 3

The recursive code follows naturally.

def fibonacci(n: int):
    if n < 0:
        raise ValueError("n must be a positive integer")
    if n == 0 or n == 1:  # base case
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Pattern matching

When faced with a puzzle, we try to find corresponding colours and shapes or force the piece into a candidate emplacement. Finding patterns is an excellent way to a solution. Take the example of the recursive Fibonacci algorithm; listing the solution for a few inputs gives you a sense of what you need to do. Another approach is to find similar problems and study their solutions. You might be able to adapt or find inspiration from them.

By understanding your problem’s dimension, you will intuitively figure out if it is solvable or intractable. The more dimensions a problem has, the harder it will be to explore the solution space. Think how finding something in one dimension is easy (a document in a folder). It starts to become hard with two dimensions (a particular pair of socks in a shallow drawer). Add a third dimension, and it becomes, really, really hard.

Remember problem complexity classes? Some problems can be solved in polynomial time, for example, sorting a list. Problems like the travelling salesperson problem belong to the NP-complete class. The variables and constraints of your problems will give you hints on which class it belongs to. If you are dealing with an NP problem, you will know that you won’t be able to find an exact solution. You will have to look into approximation techniques and take inspiration from other NP problems.

Use building blocks

Finding the shape of your input or intermediary data will help devise an algorithm around it. This opportunist method could help: run through the list of known data structures and see if they could fit your problem.

• Can I use a list?
• A linked list?
• Is it a graph problem or a tree problem?
• A dictionary or a map?
• A binary tree?
• A heap or a queue?
• Sort the data first?

Conclusion

Solving a problem is not always easy. You need to tap into your experience, knowledge, and intuition. Pasteur’s rule states that “chance favours only the prepared mind” when observing something. We can prepare ourselves by learning about other topics and running through a list of known techniques and solutions.