DS&A

Specifying Problems

We want to write algorithms, because algorithms solve computational problems. Before writing an algorithm, we need to make the problem specific enough — we need to understand exactly what our algorithm is required to do.

Here are some problems which can be solved by algorithms:

1. Reverse the contents of a list in-place.
2. Count how many times a value occurs in a list.
3. Find a shortest path between two nodes in a weighted graph.
4. Determine whether two polygons intersect each other in 2D space.

Computational problems are often phrased in terms of their inputs and outputs: what data is available, and what should the result be? Identifying the inputs and outputs for a problem is usually not difficult; we just need to find the key words in the problem statement:

1. Reverse the contents of a list in-place.
2. Count how many times a value occurs in a list.
3. Find a shortest path between two nodes in a weighted graph.
4. Determine whether two polygons intersect each other in 2D space.

Here, the inputs are highlighted blue and the outputs are highlighted red.

Once we’ve identified the inputs and outputs, it’s good to give some examples, to clarify the problem statement. Here are some:

1. Reverse the contents of a list in-place.
   • The list [1, 3, 2, 5, 4] will become [4, 5, 2, 3, 1].
   • The list ["hello", "world"] will become ["world", "hello"].
2. Count how many times a value occurs in a list.
   • The value 7 occurs 3 times in the list [1, 7, 2, 7, 7, 5, 9].
   • The value "hello" occurs once in the list ["hello", "world"].
   • The value 10 occurs 0 times in the list [1, 3, 2, 5, 4].
3. Find a shortest path between two nodes in a weighted graph.
   • The shortest path from the start to the destination is highlighted in the graph below.
     
4. Determine whether two polygons intersect each other in 2D space.
   • These two polygons intersect:
     
   • These two polygons don’t intersect:
     

Even if you already have some examples, it’s often worth inventing some yourself to get a better understanding of a problem before you solve it.

To solve these problems computationally, we must specify how to represent the inputs and outputs as data:

1. Reverse the contents of a list in-place.
   • Input: the list to be reversed.
   • Output: none.(1)
2. Count how many times a value occurs in a list.
   • Input: a list.
   • Input: the value to be counted.
   • Output: the number of occurrences, as an integer.
3. Find a shortest path between two nodes in a weighted graph.
   • Input: a weighted graph.(2)
   • Input: the start node.
   • Input: the destination node.
   • Output: a path, represented as a list of nodes beginning with the start node, and ending with the destination node.
4. Determine whether two polygons intersect each other in 2D space.
   • Input: a polygon, represented as a list of 2D vectors.
   • Input: another polygon.
   • Output: a Boolean indicating whether or not the polygons intersect.

We should also specify the types of the inputs and outputs where we can. In these examples, we identified which inputs and outputs were numbers, lists, nodes and graphs, and so on. Sometimes this may be less obvious — for example, we needed to choose how to represent a path in a graph, or a polygon in 2D space.

This is the very first step in writing an algorithm, because a function needs to have a signature:

def reverse_list(lst):
    # ...

def count_occurrences(lst, value):
    # ...

def shortest_path(graph, node_from, node_to):
    # ...

def polygons_intersect(polygon1, polygon2):
    # ...

Footnotes

1. The input will really be a pointer to the list; our function will change the contents of the list, but not its memory address. So we don’t need to return the pointer — whoever called our function already has it.
2. Actually, depending on which graph data structure is used, we may or may not need the graph as an input. If each node is an object with a list of neighbours, then that list can be used to access other nodes in the graph.

• Tags: 
• plans, problems, algorithms