For general information about assignments in this course, see assignments

In class we discussed that RowMult could not be trivially parallelized with parallel loops. Write a \(O(\log n)\) span, \(O(n)\) work divide-and-conquer version of RowMult to multiply one row of an \(n\times n\)-matrix by a \(n\)-vector. Prove that your algorithm meets the specified bounds.

Write a dynamic multithreaded algorithm to sum the numbers in an array using only parallel for, not spawn. Prove asymptotic upper bounds for the work and span of your algorithm. For full credit your algorithm should have span at most \(O((\log n)^2)\). Make sure you avoid race conditions (and explain why they are avoided); you may use up to \(O(n)\) extra memory for intermediate results. Don’t use any extra features from OpenMP, only the basic parallel for in the textbook.