CSE 305 - Tutorial 1 - Thread basics in C++

In this tutorial, you will be asked to implement functions described below. The exact definitions and automated tests are given to you in the following archive. The provided code can be compiled by running make grader. Then the autotests can be run by ./grader. You are encouraged to study the demo code presented at the beginning of the TD.

Your task is to fill the implementations of the functions in td1.cpp and submit it on this page by 23:59 March 26. The solution will be graded first by autograder (40% of the grade) and then for a secret subset of the problems manually (remaining 60% of the grade). You are allowed (and encouraged) to revise your code based on the output of autograder and resubmit again before the deadline.

In the following four problems, arguments begin and end are the start and end iterators of a vector of long double and an argument num_threads is an integer. All the functions below should do their computation on the array using num_threads threads, where each thread is responsible for a portion of the vector.

Implement a function SumParallel(begin, end, f, num_threads) (similar to SumParallel in demo), where f is a function of signature long double (long double). The function should compute the sum \(f(a_1) + \ldots + f(a_n)\), where \(a_1, \ldots, a_n\) are the values in the vector.
Implement a function MeanParallel(begin, end, num_threads) that computes the average of the numbers in the vector.
Implement a function VarianceParallel(begin, end, num_threads) that computes the variance of the numbers in the vector.

Hint use the following formula for the variance \(\mathrm{Var}(X) = E (X^2) - (EX)^2\), where \(E\) stands for the expectation (which is the average in our situation).

Upload your file td1.cpp:

Upload form is only available when connected

Implement a function CountMinsParallel(begin, end, num_threads) counting how many times the minimal value occurs in the vector of integers between the iterators begin and end. Each thread should traverse only a part of the input vector, in particular, it is not allowed to compute the global minimum within one thread.
Implement a function FindParallel(begin, end, target, num_threads) that takes the start and end iterators of a container and search for the target value in parallel using num_threads threads. Make a shared boolean variable so that once one of the threads has found the value, the others stop the search.

Upload your file td1.cpp:

Upload form is only available when connected

(optional exercise) We have discussed that STL containers are not thread-safe in the sense that, in the presence of a writer there should not be any readers. This is true even if reading and writing is performed on different parts of the container. Write a code demonstrating that pushing new elements to a vector may interfere with concurrent reading of already existing elements.
(optional exercise; requires some specific insights in STL containers) Even further, think of a type T such that std::vector<T> would not be thread-safe with respect to concurrent writers writing to different locations in the vector.

There are no automatic tests for this exercise but you are encouraged to submit your code (including some comments on what behavior you observe) in a file vector_safety.cpp:

Upload form is only available when connected