1. Parallelize the program of finding the sum of n numbers (a1+a2+...+an) using n/2 processors. (1)...
1. Parallelize the program of finding the sum of n numbers (a1+a2+...+an) using n/2 processors.
(1) Draw the diagram;
(2) Find the numbers of operations for the implementations of the sequential algorithm and the parallel program;
Homework Answers
Algorithm for summation of using n processors in parallel-
int arr[n],summation=0
for i=0 to n-1 in parallel
summation=a[i]
Time Complexity - O(n)
Algorithm for summation of using n/2 processors in parallel-
for i = 0 to n-1 do in parallel
temp[i] = a[i];
for i = 0 to n-1 do in parallel
for j = 1 to log n do
if (i mod 2^j == 2^j - 1) then
temp[i] = temp[i] + temp[i - 2^(j-1)];
sum = temp[n-1];
Time Complexity - O(logn)
Add Answer to:
1. Parallelize the program of finding the sum of
n numbers
(a1+a2+...+an)
using n/2 processors.
(1)...
The input consists of n numbers a1, a2, . . . , an and a target...
The input consists of n numbers a1, a2, . . . , an and a target value t. The goal is to determine in how many possible ways can we add up two of these numbers to get t. Formally, your program needs to find the number of pairs of indices i, j, i < j such that ai+aj = t. For example, for 2, 7, 3, 1, 5, 6 and t = 7, we can get t in two...
(C programming) Given a sequence of numbers a1, a2, a3, ..., an, find the maximum sum...
(C programming) Given a sequence of numbers a1, a2, a3, ..., an, find the maximum sum of a contiguous subsequence of those numbers. Note that, a subsequence of one element is also a contiquous subsequence. Input The input consists of multiple datasets. Each data set consists of: n a1 a2 . . an You can assume that 1 ≤ n ≤ 5000 and -100000 ≤ ai ≤ 100000. The input end with a line consisting of a single 0. Output...
You are given a set of integer numbers A = {a1, a2, ..., an}, where 1...
You are given a set of integer numbers A = {a1, a2, ..., an}, where 1 ≤ ai ≤ m for all 1 ≤ i ≤ n and for a given positive integer m. Give an algorithm which determines whether you can represent a given positive integer k ≤ nm as a sum of some numbers from A, if each number from A can be used at most once. Your algorithm must have O(nk) time complexity.
Given the following algorithm: Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a)...
Given the following algorithm:
Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a) Return(i) Return(-1) 3, -1, 2,9, 36,-7, 6,4 a) What is the correct output of the Algorithm with the following input: a1, a2,..an b) What is the asymptotic worst-case time complexity of the Algorithm?
Algorithnm Input: a1, a2,...,an, a sequence of numbers...
1. Write a program that reads in two arrays (a1 and a2) of numbers and creates...
1. Write a program that reads in two arrays (a1 and a2) of numbers and creates a new array (a3) of numbers such that the new array contains all the unique numbers of a1 and a2. Assume the input array elements are unique elements. In the main function, ask the user to enter the length of each array, declare and reads in the numbers for each array, and calculate and display the output array. Example input/output #1: Enter the length...
(1) Let a (.. ,a-2, a-1,ao, a1, a2,...) be a sequence of real numbers so that f(n) an. (We may eq...
(1) Let a (.. ,a-2, a-1,ao, a1, a2,...) be a sequence of real numbers so that f(n) an. (We may equivalently write a = (abez) Consider the homogeneous linear recurrence p(A)/(n) = (A2-A-1)/(n) = 0. (a) Show ak-2-ak-ak-1 for all k z. (b) When we let ao 0 and a 1 we arrive at our usual Fibonacci numbers, f However, given the result from (a) we many consider f-k where k0. Using the Principle of Strong Mathematical Induction slow j-,-(-1...
: Let a1, a2, a3, . . . be the sequence of integers defined by a1 = 1 and defined for n ≥ 2 by the recurrence relation a...
: Let a1, a2, a3, . . . be the sequence of integers defined by a1 = 1 and defined for n ≥ 2 by the recurrence relation an = 3an−1 + 1. Using the Principle of Mathematical Induction, prove for all integers n ≥ 1 that an = (3 n − 1) /2 .
Let n be a positive integer. We sample n numbers a1, a2,..., an from the set...
Let n be a positive integer. We sample n numbers a1, a2,..., an from the set {1,...,n} uniformly at random, with replacement. We say that picks i and j with are a match if ai = aj, i < j. What is the expected total number of matches? Use indicators.
float useless(A){ n = A.length; if (n==1) { return A[@]; let A1,A2 be arrays of size...
float useless(A){ n = A.length; if (n==1) { return A[@]; let A1,A2 be arrays of size n/2 for (i=0; i <= (n/2)-1; i++){ A1[i] = A[i]; A2[i] = A[n/2 + i]; for (i=0; i<=(n/2)-1; i++){ for (j=i+1; j<= (n/2)-1; j++){ if (A1[i] == A2[j]) A2[j] = 0; b1 = useless(A1); b2 = useless (A2); return max(b1,b2); What is the asymptotic upper bound of the code above?
Given the following algorithm:
Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a) Return(i) Return(-1) 3, -1, 2,9, 36,-7, 6,4 a) What is the correct output of the Algorithm with the following input: a1, a2,..an b) What is the asymptotic worst-case time complexity of the Algorithm?
Algorithnm Input: a1, a2,...,an, a sequence of numbers...
(1) Let a (.. ,a-2, a-1,ao, a1, a2,...) be a sequence of real numbers so that f(n) an. (We may equivalently write a = (abez) Consider the homogeneous linear recurrence p(A)/(n) = (A2-A-1)/(n) = 0. (a) Show ak-2-ak-ak-1 for all k z. (b) When we let ao 0 and a 1 we arrive at our usual Fibonacci numbers, f However, given the result from (a) we many consider f-k where k0. Using the Principle of Strong Mathematical Induction slow j-,-(-1...
float useless(A){ n = A.length; if (n==1) { return A[@]; let A1,A2 be arrays of size n/2 for (i=0; i <= (n/2)-1; i++){ A1[i] = A[i]; A2[i] = A[n/2 + i]; for (i=0; i<=(n/2)-1; i++){ for (j=i+1; j<= (n/2)-1; j++){ if (A1[i] == A2[j]) A2[j] = 0; b1 = useless(A1); b2 = useless (A2); return max(b1,b2); What is the asymptotic upper bound of the code above?
Most questions answered within 3 hours.
-
A check-processing center uses exponential smoothing to forecast
the number of incoming checks each month. The...
asked 2 minutes ago -
Teams with high levels of ______ and ______ deal with task
conflict better than those without...
asked 13 minutes ago -
Create a C++ project called lab3b and add the following source
code init_struct.cpp to the project....
asked 24 minutes ago -
12.
A budget that can be easily adjusted to show budgeted revenues,
costs, and cash flows...
asked 32 minutes ago -
________ unemployment changes slowly and depends on
________.
Select one:
a. Frictional; the rate at which...
asked 1 hour ago -
These surveys collect information in low- and
middle-income countries regarding the total fertility rate and the...
asked 1 hour ago -
I need to determine the concentration of hydrogen peroxide in a
solution using titrimetric analysis
25...
asked 1 hour ago -
Your are the Vice-President of operations for a New Orleans food
chain. In the aftermath of...
asked 1 hour ago -
Create a flowchart and a program; test the program. Program
Requirements.
- There are 10 members...
asked 1 hour ago -
Which of the following is not a sensory receptor?
a. a hair cell
b. a rod
c. a...
asked 1 hour ago -
Does the launch speed depend significantly upon the launching
angle? Is it reasonable?
asked 2 hours ago -
A disc of moment of inertia 3.00 kgm2 is rotating with angular
velocity 2.00 rad/s about...
asked 1 hour ago