Computer science is essentially the study of computational problems and how to solve them using the minimal amount of resources. A computational problem is a specification of the relation between input and output. A solution to the problem is an executable algorithm that realizes that relation. That is, given a particular input to the algorithm (which is really an instance of the problem), the algorithm will process it and produces the required output(1). Sorting is a typical example of a computational problem. Some problems can be solved quite easily even by people who know very little about computer science, while others may require a tremendous amount of ingenuity and/or experience.
There are many problem-solving techniques that are usually studied in a course about algorithms. However, I found that all of these techniques can be classified into the following three classes:
- Incremental Construction: Techniques of this type start with a partial solution and then perform some processing to expand it until a full solution is reached. For example, to sort an array of numbers, we can find the smallest number of the input array and put it as the first element of the output array. Then find the next smallest element and put in the next empty slot of the output array. This process is continued until all the elements have been processed and output array is the solution.
- Iterative Improvement: Techniques of this type start with a full potential solution. The algorithm attempts to gradually improve the solution until either the desired solution is found or a dead end has been reached. A dead end could be either the situation that no further improvement could be made or a timeout. Finding the smallest element in an unsorted array is solved using an iterative improvement technique. The first element is considered to be the smallest element. The rest of the elements are examined until a smaller element is found. When the all elements have been examined, the current smallest element becomes the solution. The sorting algorithm that I presented above is a variant of selection sort. Most sorting algorithms including selection sort are actually iterative improvement techniques.
- Mathematical Formulation: Techniques of this type express the output as a mathematical function of the input that does not use notations representing iteration or recursion. For example, finding the smallest element of a sorted array is just the first element of the array.
Most problems require solutions that are hybrid where the overall technique is of some type but it uses other techniques of different types to solve sub-problems. For example, the explicit solution to the N-Queens puzzle is an incremental construction technique that at each step, a mathematical formula is used to compute the location of the next queen.
These problem-solving classes have many sub-classes. For example, a greedy algorithm is incremental construction technique that makes the optimal decision locally at each step and hope that a globally optimal solution will be reached at the end.
When you attempt to solve a problem, you have to think about how to represent inputs and outputs and the basic computations that can be used to mutate state in a way that can be handled by an algorithm. The representation usually dictates the type of the technique that solves the problem. Sometimes with a particular representation, you may find a solution that is not efficient enough or maybe you may not even be able to see a path towards a solution. In such cases, it might be helpful to design a different representation that potentially provides more insight on how to solve the problem. The way you approach a problem to solve is called a problem-solving strategy.
This blog post constitutes a short reference on how to solve problems. In the future, I will probably write about specific problems and how to solve them.
- Do not confuse between a solution to a problem and a solution to an instance of it. A solution to a computational problem is an algorithm. A solution to an instance of a problem is the output that the algorithm produces given that instance.↩