**Even parity checking**-
- Description
- Determine if a list of boolean values has an even number of true-values.
- Author
- Roland Olsson (inspired by several papers at GP-98 discussing this problem).
- Complexity
- 36 bits
- Creation time
- 12 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Reversing a list**-
- Description
- Reverse a list of integers.
- Author
- Roland Olsson
- Complexity
- 47 bits
- Creation time
- 570 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Duplicate checking**-
- Description
- Determine if a list is a set i.e., does not contain duplicates.
- Author
- Roland Olsson
- Complexity
- 65 bits
- Creation time
- 116 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**List delete min**-
- Description
- Delete the minimum element from a list.
- Author
- Roland Olsson
- Complexity
- 73 bits
- Creation time
- 3905 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Cartesian product**-
- Description
- Given two lists
`Xs`and`Ys`, compute a list of all pairs`(X,Y)`such that`X`is in`Xs`and`Y`is in`Ys`. - Author
- Roland Olsson
- Complexity
- 78 bits
- Creation time
- 978 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Intersecting two lists**-
- Description
- Given two lists
`Xs`and`Ys`, find all elements that occur in both`Xs`and`Ys`. - Author
- Roland Olsson
- Complexity
- 88 bits
- Creation time
- 45636 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**String comparison**-
- Description
- This problem was inspired by the C library function
`strcmp`

. Assume that the input is two strings`X`and`Y`. If`X`is less than`Y`, return`less`

. If`X`is equal to`Y`, return`equal`

. If`X`is greater than`Y`, return`greater`

. - Author
- Roland Olsson
- Complexity
- 93 bits
- Creation time
- 49762 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Sorting a list**-
- Description
- Sort a list of integers in ascending order.
- Author
- Roland Olsson
- Complexity
- 96 bits
- Creation time
- 1529 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Permutation checking**-
- Description
- Given two lists
`Xs`and`Ys`, determine if`Xs`is a permutation of`Ys`. - Author
- Roland Olsson
- Complexity
- 100 bits
- Creation time
- 58849 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Locating a substring**-
- Description
- This problem was inspired by the C library function
`strstr`

. Assume that the input is two strings`X`and`Y`. If`Y`does not occur in`X`, return`none`

. If`Y`occurs in`X`, return the longest suffix of`X`that starts with`Y`. - Author
- Roland Olsson
- Complexity
- 103 bits
- Creation time
- 499352 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Binary search tree insertion**-
- Description
- Insert an element into a binary search tree of integers.
- Author
- Roland Olsson
- Complexity
- 115 bits
- Creation time
- 12271 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Multiplying unsigned binary numbers**-
- Description
- Multiply two natural numbers of arbitrary length and in binary form. Note that the specification contains an auxiliary adding function which was synthesized by the ADATE system before the specification was written.
- Author
- Roland Olsson
- Complexity
- 117 bits
- Creation time
- 44726 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Simplifying a polynomial**-
- Description
- Given a polynomial represented as a list of coefficient-exponent pairs, return an equivalent polynomial without duplicate exponents.
- Author
- Roland Olsson
- Complexity
- 126 bits
- Creation time
- 74589 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Transposing a matrix**-
- Description
- Transpose a matrix represented as a list of lists such that each sublist is a row in the matrix.
- Author
- Roland Olsson
- Complexity
- 155 bits
- Creation time
- 41789 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Permuting a list**-
- Description
- Compute a list of lists containing all permutations of a given list. Note that the output evaluation function is defined using the synthesized program for duplicate checking and the synthesized program for permutation checking.
- Author
- Roland Olsson
- Complexity
- 163 bits
- Creation time
- 403808 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Binary search tree deletion**-
- Description
- The input is an integer
`X`and a binary search tree`Xs`. The output is a binary search tree with the same elements as`Xs`but with one occurrence of`X`removed if there is any`X`in`Xs`. - Author
- Roland Olsson
- Complexity
- 169 bits
- Creation time
- 341670 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Path finding**-
- Description
- Assume that a directed graph is represented as a list of node pairs such
that each pair represents an edge in the graph. The input ia a start node,
a goal node and the graph. The output is
`none`

if there is no path from the start node to the goal node. The output is`some`

`Xs`if there is a path`Xs`from the start node to the goal node. This path is represented as a list of nodes. - Author
- Roland Olsson. The problem was suggested by Ulf Nilsson.
- Complexity
- 192 bits
- Creation time
- 815421 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Adding unsigned binary numbers**-
- Description
- Add two natural numbers of arbitrary length and in binary form.
- Author
- Roland Olsson
- Complexity
- 194 bits
- Creation time
- 740439 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file

**Intersecting two rectangles**-
- Description
- This problem is the same as finding the overlap between two windows in a GUI.
Assume that the input is two parallel rectangles
`A`and`B`. If`A`and`B`do not overlap, return`none`

. If`A`overlaps`B`, return the overlap. - Author
- Roland Olsson
- Complexity
- 239 bits
- Creation time
- 220926 seconds on a 200 MHz PentiumPro
- The best individual
- The genealogical chain leading to the best individual
- The specification file
- The log file