Jan Kończak

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Assignment 1 =====

**Deadline: May 31st.**



[[https://en.wikipedia.org/wiki/Collatz_conjecture|Collatz conjecture]] is an
open mathematical problem.
\\
It boils down to a question whether the following procedure will terminate for
any value of ''x'': 
<code c>
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
  }
}
</code>

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.**

-----


===== Assignment 2 =====


**Deadline: June 9th.**

Write a **thread-safe
[[https://en.wikipedia.org/wiki/Associative_array|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.)

<small>You may use ''valgrind --tool=drd //progname//'' and ''valgrind --tool=helgrind //progname//'' to test your program.</small>



~~META:
language = en
~~
Jan Kończak

User Tools

Site Tools

Page Tools
