Programming Assignment 2 - Tri-partitioning

Due Date

. See the assignment turn-in page (last modified on 14 January 2006) for instructions on turning in your assignment.

Background

The Problem

struct answer {
  unsigned v1, v2, v3, moves;
  }

typedef std::vector<unsigned> ivec;

answer tripartition(ivec iv1, ivec iv2, ivec iv3);

that accepts three vectors of non-negative integers and determines the minimum number of moves required to tri-partition the vectors. A move occurs whenever a number is shifted from one vector to a different vector (shifting a number within the same vector is not a move). The answer returned by tripartition() should contain the following values:

• v1: the value modulo 3 of any element in iv1.

• v2: the value modulo 3 of any element in iv2.

• v3: the value modulo 3 of any element in iv3.

• move: the number of moves required to three-sort the vectors.

If there is more than one minimal tri-partition possible, tripartition() can return any of them.

The answer struct, the ivec typedef and the tripartition prototype are defined in tripartition.h in the assignment directory /export/home/class/cs-306/pa2.

You can test your procedure by compiling it with the file

/export/home/class/cs-306/pa2/main.o

The -s command-line option takes an integer argument and uses it as the seed for the random-number generator. You can run your code repeatedly on the same set of randomly-generated data by passing in the same value with -s on each execution. The default is to generate a different set of randomly-generated data with each execution.

The source file for main() will not be made available because it contains my answer to the problem.

Your implementation of tripartition() should not exploit any extra properties of the input data; I'll be generating different input data when I test your assignments.

To be correct, your solution must be efficient; that is, you solution should take no more than twice the execution time my solution takes on the same input. The test executable keeps track of execution times. The -t command-line option prints the execution time taken by your version of tripartition().