Dana Vrajitoru
B424 Parallel and Distributed Programming

B424/B524 Homework 5

Due date: Thursday, October 1, 2020.

Divide and Conquer Example

The following files contain an implementation of the sum of the elements of an array in a divide and conquer approach:
div_conquer.cc
div_conquer.h
main.cc
Makefile

Compile the program with the command make. The name of the executable will be psum.

Ex. 1. Target Search

The program above generates an array randomly and computes the sum of its elements. Both the linear and the hierarchical methods for collecting and combining the data are implemented.

Rewrite the program such that it asks the user for the range of the values in the array, then for a target value to search for in the array.

Implement a multi-threaded target search function using the model of the prime number function that uses a divide and conquer approach with interruption and that can be found in the PowerPoint slides. Each thread should look for a target in a part of the array and communicate the index where it finds it using a global variable. Initialize this global variable as -1, which is a flag we'll use to signify that the target was not found.

Implement the program in such a way that when one of the threads finds the target, the others become aware of it and stop looking.

Have the master thread output the array and the index where the target was found at the end for verification.

Homework Submission

Upload: to Canvas, Assignments, Homework 5, all the files that you modify or add (including the Makefile if you've changed it).