# Introduction

For general information about assignments in this course, see assignments

# Parallelize RowMult

In class we discussed that `RowMult`

could not be trivially
parallelized with parallel loops. Write a $O(\lg n)$ span, $O(n)$
work divide-and-conquer version of `RowMult`

to multiply one row of an
@@math:n\times n@@-matrix by a @@math:n@@-vector. Prove that your algorithm meets the
specified bounds.

# Sum with parallel for

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 @@math:O(\lg(n)^{2})@@ and work at most
$O(n\lg{}n)$. 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.

# Single writer race

Consider the following racy pseudocode from the lectures

```
x ← spawn foo(x);
y ← bar(x);
sync
return x+y
```

For at least two distinct (in terms of results) possible execution orders (at the procedure call level), give equivalent non-racy pseudocode.

Is there a non-racy version that has some potential parallelism? If so, does this version match the output of the serialized code? If there is no non-racy version with potential parallelism, why not?