Due: 2020-11-26 11:59 PM

Q1 Matrix times vector

Write a multithreaded algorithm to compute the product of an n × n matrix and an n-vector.

• a) Write a O(log n) span algorithm to multiply one row of a matrix by a vector.

• b) Use a parallel for loop, along with your algorithm from part (a) to multiply a matrix by a vector.

• c) Give asymptotic upper bounds on the work and span of the resulting algorithm.

Q2 Divide and flounder

Consider the following parallel search algorithm.

function ParSearch (A, p, q, k)
  If p > q return FALSE
  If A[p] = k  return TRUE
  if p = q return FALSE
  right ← spawn ParSearch(A, p + 2, q, k)
  left ← ParSearch(A, p+1,p+1, k)
  sync
  return left OR right
end function

• Draw a computation DAG for ParSearch(A,1,4,k) for some k ∉ A
• Give recurrences for span and work of this algorithm
• Give asymptotic lower bounds for the work and span of this algorithm.