Jan Kończak

Deadline: May 31st.

Collatz conjecture is an open mathematical problem.
It boils down to a question whether the following procedure will terminate for any value of x:

typedef uint64_t natural_number;
void collatz(natural_number x) {
  while (x != 1) {                 // until you reach 1,
    if (x % 2)                     // if the number is odd,
      x = 3 * x + 1;               // multiply it by three and add one,
    else                           // else, if the number is even,
      x /= 2;                      // divide it by two
  }
}

For instance, collatz(3) will go through the following numbers:
      3→10→5→16→8→4→2→1
so it needs 7 steps to reach 1 from 3.
Notice that 32 needs only 5 steps, but 27 needs 111 steps.

Your assignment is to write a computer program that will take as an argument an integer MAX_STEPS and will run until it finds five smallest numbers that need S steps to go down to 1 for every integer S lesser than MAX_STEPS and larger than 10.

The program must be written so that it can be:

• run multiple times in parallel,
• stopped and started at will.

So, the program must use shared memory to store the results and disseminate the numbers to test among running processes.
Obviously, the results must be correct.

If the program is restarted with MAX_STEPS greater than for the first time, it shall print an error.

There is one strict performance requirement: several instances of the program must compute faster than a single-threaded brute-force program doing the same job.

Deadline: June 9th.

Write a thread-safe associative array (key-value map) that offers the following operations:

• insert(k,v) - associates a key k with a value v
• get(k) - if k is present in the array, returns the value associated with it; else indicates that there is no such key
• poll(k) - if k is present in the array, returns the value associated with it;
  else waits until the key k is added and then returns a value associated with it
• count() - returns the number of items (key-value pairs)
• remove(…) - removes an item
• operations that allow iterating over all key-value pairs: first(), next(…), last() (or equivalent)
  The order in which the elements are traversed does not matter.
  Notice that you need to make the iterating procedure thread-safe!
  

You may extend the API of the associative array whenever needed. You may choose any type for key and value (e.g., int).

Moreover, write an application that tests the associative array by running the following operations in parallel:

• iterating through all key-value pairs
• adding a key-value pair and removing it
• adding a number of key-value pairs and then removing all of them
• getting values of randomly chosen keys
• polling for values of randomly chosen keys

(You can run each of these operations in a loop, one thread per one loop.)

You may use valgrind --tool=drd progname and valgrind --tool=helgrind progname to test your program.