All of the following questions are taken from 

        John Feo, "A Comparative Study of Parallel Programming Languages:
             The Salishan Problems", North-Holland, 1992. Page 5, ff.

The statement of the problems has be "TeX'd" in order to convey the problem
as clearly as possible.

Problem 1. Hamming's Problem (extended) 

  Given a set of primes $\{a,b,c,...\}$ of unknown size and an integer $n$,
output in increasing order and without duplicates all integers of the
form
\[
         a^i \times b^j \times c^k \ldots \leq n
\]
Observe that if $r$ is in the output stream then
\[
         a \times r, b \times r, c \times r \ldots \leq n
\]
are also in the output stream.

  The problem tests a language's ability to express recursive stream
computations and producer/consumer parallelism, and to support dynamic task
creation.

2. Parafins Problem

  Given an integer $n$, output the chemical structure of all paraffin
molecules for $i \leq n$, without repetition and in order of increasing size.
Include all isomers, but no duplicates. The chemical formula scheme for
paraffin molecules is $C_t H_{2t+2}$. You may choose any representation for the
molecules you wish as long as it clearly distinguishes isomers.

3.The Doctor's Office

 Given a set of patients, a set of doctors, and a receptionist, model the
following interactions: initially patients are all well, and all doctors are
in a FIFO queue awaiting sick patients. At random times, patients become sick
and enter a FIFO queue for tratement by one of the doctors. The receptionist
handles the two queues, assigning patients to doctors in a first-in-first-out
manner. Once a doctor and patient are paired, the doctor diagnoses the illness
and cures the patient in a random amount of time. The patient is then released,
and the doctor rejoins the doctor's queue to await another patient. The
output of the problem is intentially left unspecified.

  This is neither an event-driven nor a time-driven simulation. There is
no global knowledge, no knowledge of when events will occur, no global
clock, and no global communications. You may use any method you wish to decide
when a patient becomes sick and how long a patient sees a doctor. The inter-
actions of the patients, doctors, and receptionist should be true to life.
Our intent is to test each language's ability to program a set of concurrent,
asynchronous processes with circular dependencies.

4. Skyline Matrix Solver

  Solve the system of linear equations,
\[
              Ax = b
\]
without pivoting where $A$ is an $n\times n$ skyline matrix. A skyline
matrix has nonzero values in row $i$, in columns $k$ through $i$ for
$1 \leq k \leq i$ and nonzero values in column $j$ in rows $k$ through
$j$ for $1 \leq k \le j$. The values of $k$ are stored in two vectors:
$row$ and $column$. For example, let A be the below matrix


          1  0  0  1  0  0  0
          0  1  0  1  0  1  0
          0  1  1  1  1  1  0
          0  0  0  1  1  1  0
          0  1  1  1  1  1  0
          0  0  0  1  1  1  0
          0  0  0  0  0  0  1

then $row = \{1,2,2,4,2,7\}$ and $column=\{1,2,3,1,3,2,7\}$. You may
assume any input form you wish for $A, b, row,$ and $column$.

[\ldots] We include the problem to test the ability of each language to define
array structres that include nonessential elements ( {\em i.e.,} the zeros),
and given those structures, support parallel and iterative array computations
efficiently ({\em i.e.,} avoid the computations involving the zeros).