Computational problem

Computational problem #

A computational problem is (usually) specified as:

  • a set of possible inputs, and
  • the expected outputs (for these inputs).

Problem vs algorithm #

For instance, here is a problem that you may have encountered already:

  • Input: a sorted array $A$ of integers, an integer $a$
  • Output: true if $a$ appears in $A$, false otherwise

There are (infinitely) many algorithms that can solve this problem. But some of them are more efficient than others. Efficiency (a.k.a. computational cost) refers to the time and/or memory needed to execute an algorithm, expressed as a function of the size of the input (more on this later).

Can you think of (or do you already know) an algorithm that can solve this problem efficiently? Why is it efficient?

Algorithm. Let $n$ be the size of $A$, and let us assume for simplicity that arrays are $1$-indexed and that $A$ is nonempty.

  • If $n = 1$, then check whether $A$[1] $= a$.
  • Otherwise:
    • check whether $A[n/2] = a$ (where “$/$” is integer division, rounded up or down if $n$ is odd),
    • depending on the result, repeat on either the left or the right half of $A$.

Cost. If $A$ has length $n$, then the number of iterations of the procedure is (in the order of) $\log_2 n$ in the worst case (e.g. if $a$ does not appear in $A$).

Here is another problem that you may know:

  • Input: an array of integers
  • Output: an array with the same values, but sorted in ascending order

And yet another:

  • Input: a solvable grid of sudoku
  • Output: the same grid, solved

Note. A problem specifies what a program should do, not how to do it. In other words, a computational problem is not an algorithm.

For instance, the following is not a computational problem:

  • Input: an array of integers.
  • Algorithm: initialize a counter to $1$. Then iterate through the array, and:
    • increment the counter each time two consecutive numbers are encountered, or
    • reset the counter to $1$ otherwise.

Which problem does this algorithm solve? Is this algorithm efficient?

  • Input: an array $A$ of integers
  • Output: the length of the longest suffix of $A$ that consists of consecutive numbers

Formulating a problem #

When developing a project, it can be helpful to express some sub(tasks) as computational problems. This is also a common way to document your code.

For instance the Javadoc of a class may consist of computational problems (e.g. the Javadoc for the method endsWith of the class String in Java).

When formulating a problem, make sure that:

  • the output is specified for all inputs, and
  • the formulation is non-ambiguous, meaning that it should clearly specify whether any given pair (input, output) is correct.

Consider the class Unit (and its subclasses), as defined in the section about inheritance. The following problem is not properly defined. Can you see why?

  • Input: a nonempty array A of instances of the class Unit
  • Output: the unicorn with highest health in A

There may be no unicorn in A, or several healthiest unicorns.

The following problem is not properly defined. Can you see why?

  • Input: a (finite) family of (finite) sets
  • Output: the smallest set that has a nonempty intersection with each of the input sets (where “smallest” here refers to the size of a set)

For instance, for the input

{ {a,c,k}, {a,b}, {a,m}, {c,d,f}, {c,e} }

the expected output is

{a,c}

Some inputs admit more than one solution (the simplest example is the input {{a,b}}).

Note. A problem may admit several outputs for the same input without being ambiguous. For instance:

  • Input: a graph G, two nodes s and t in G,
  • Output: one of the shortest paths from s to t in G if any, and null otherwise.

A problem may be undecidable, meaning that for any algorithm attempting to solve this problem, there (provably) exist (infinitely many) inputs for which the algorithm either produces an incorrect output or does not terminate.

A problem may be decidable but intractable, meaning that (provably) no efficient algorithm can solve it (where cost is once again measured as a function of the size of the input).