Computational problems

We use computing to solve computational problems. A computational problem should be specified by a name, description of its inputs, and description of its outputs including how the inputs and outputs are related. The specification guides the interface provided by the function(s) solving the problem.

Sorting #

The problem of sorting a sequence of elements can be specified as:

Name
SORT
Input
A sequence of elements. There is a predetermined ordering relation among the elements.
Output
The same sequence of elements in ascending order.

We can also make the specification more precise by using mathematical notation.

Name
SORT
Input
  • A sequence \(S = (a_0, \dotsc, a_{n-1})\) where each \(a_i\in A\) for some set \(A\).
  • A total order \(\leq\) on the set \(A\).
Output
A sequence \(T = (b_0, \dotsc, b_{n-1})\) that satisfies:
  • The sequence \(T\) can be obtained from \(S\) by only rearranging the elements of \(S\).
  • \(b_0 \leq b_1 \dotsc \leq b_{n-1}\).

As with all writing, the specification you use should depend on the audience. The simplest specification that conveys the full information is the best one. The above specification leads to the following C interface (simplified to deal with only integers):

void sort(int a[], int n, bool (*leq)(int a, int b));

Notice that the ordering is a parameter. This allows us to use the same function to sort integers based on ascending or descending order.

We now discuss some common pitfalls while defining computational problems.

Selection #

Consider the problem of finding the minimum value in a sequence.

Name
MIN
Input
A sequence \(S = (a_0, \dotsc, a_{n-1})\) where each \(a_i\) is an integer.
Output
The smallest integer in the sequence.

The above definition looks Ok. But, it misses a corner case.

What is the output of MIN when the sequence is empty?

The corner case can be avoided by making one of the given choices. This corrects the definition. Let us discuss each choice.

If we define the empty sequence input as an error, there are two ways as follows to define this in C.

int min(int a[], int n);
bool min(int a[], int n, int *output);

In the first version, the function must abort the program if n = 0. In this case, the caller of the function should always ensure that the sequence is non-empty before calling min. In the second version, the returned bool indicates whether *output contains a valid minimum. This definition prevents usage of the function directly in expressions such as min(a, 5) + 3. We note that the Python programming language throws an error when the sequence is empty.

The choice of returning INT_MIN for empty sequence is the best design as it is a natural identity for the min operation in C. Unlike Python which has true integers, INT_MIN is the smallest integer in C.

Searching #

Consider the problem of searching for an element in a sequence. Let us call this problem SEARCH.

What should be the output of SEARCH?

All choices above are well-defined. There is no corner case that we are missing. However, these interfaces differ in their usability. Consider the first one:

bool search(int haystack[], int n, int needle);

The only thing that this function will allow us to do is to check whether or not needle is present in haystack or not. Any solution that finds the needle in the haystack will also figure out where the needle is in the haystack. So this function is throwing away information that it has already obtained and is probably useful to the caller.

The second choice leads to the following prototype.

int search(int haystack[], int n, int needle);

It returns the index, which is a value in \([0,n)\) if the element is found and \(-1\) otherwise. The value \(-1\) is never a valid index. Using this function in arithmetic expressions may inadvertently lead to problems. Consider an expression such as a[search(a, n, v)+1] to access the element next to the needle. This will access a[0] if the element is not found. This may or may not be what the programmer intended. This ambiguity is caused by the function not requiring the caller to handle two separate cases separately – found and not found.

The third choice is:

bool search(int haystack[], int n, int needle, int **data);

This is better than the two choices above. But, the caller has to check for the return value always before accessing the output parameter thereby creating a dependency between two pieces of data. Here is some sample code on how to find an element and increment it by one in the sequence.

int *foo;
bool found = search(haystack, n, needle, &foo);
if (found) {
  *foo += 1;
}

The person writing search() also has to deal with the case where data is NULL. This further complicates the specification of the function.

The final choice:

int *search(int haystack[], int n, int needle);

is the best one. NULL is a natural return value signaling absence of data. The return value can be directly used to access the found element. If the element is not found, any attempt to access it will immediately crash the program. The code using this function will look like.

int *foo = search(haystack, n, needle);
if (foo) {
  *foo += 1;
}

which is less verbose and less ambiguous than the previous one. This is also the choice made by C standard library function bsearch, for example.

To summarize, the following points should be kept in mind when defining computational problems.