# A Library of Parallel Algorithms

This is the toplevel page for accessing code for a collection of parallel algorithms. The algorithms are implemented in the parallel programming language NESL and developed by the Scandal project. For each algorithm we give a brief description along with its complexity (in terms of asymptotic work and parallel depth).

In many cases the NESL code is set up so you can run the algorithm using our FORMs bases interface. Feel free to change the data or the algorithms and submit the modified versions. Note that some of the algorithms have stated restrictions on the input (e.g. must be of even length).

We also have a collection of parallel algorithm animations for some of the algorithms described off of this page. These animations require that you use X11.

Note: We are currently working on this page. At present some of the descriptions and documentation on the functions is quite terse. We believe they all work, however, so if you find one that does not, please report it.

## Scan

The scan operation, also called all-prefix-sums takes a binary associative operator an identity function and an arry and returns a new array with in which each element has the sum of all previous elements (sum is defined relative to the associative operator). For example
```  scan(+, 0, [2, 8, 9, -4, 1, 3, -2, 7]);
```
is
```  [0, 2, 10, 19, 15, 16, 19, 17]
```

## List Ranking

List ranking takes a linked list and returns for each element in the list its position in the list. The positions give the distance from the tail of the list. We represent lists using arrays of integers in which each integer represents the index of the next element in the list. We terminate lists with a self pointer. For example, the array
```  [2, 5, 1, 3, 7, 6, 6, 3]
```
represents the two lists
```  0 -> 2 -> 1 -> 5 -> 6
4 -> 7 -> 3
```

## Sorting

There are many parallel sorting algorithms. Here we give a sampling of some of them.

## Medians

Here we consider the more general problem of finding the kth smallest element in a set. It is well know that this problem can be solved in O(n) time sequentially. Here we consider two algorithms that both require O(n) work, although for the first this is expected case and for the second it is with high probability.

## String Matching

The string matching problem takes a TEXT string and a PATTERN string and finds all the positions in which the pattern appears in the text.

## Other String Operations

Here we consider various operations on strings, such as lexicographically comparing two strings, breaking a string of characters into lines, and matching parentheses.

## Connected Components

The connected-components problem takes an undirected graph and returns all the components that are connected by an edge. For a graph with n vertices and m edges, this problem can be solved in O(n+m) time sequentially using either depth-first-search or breadth-first-search. The parallel algorithms are based on the idea of contracting the graph.

## Spanning Trees

Spanning-tree algorithms are similar to those for connected-components, except that spanning-tree algorithms need to keep track of which edges are used for contraction and they do not need to expand the graph back out.