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

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

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

Analyze the work and span of the resulting algorithm.

**2** 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
- Solve the recurrences

**3** (ex 27.1-7 from Cormen et. al) Consider the following multithreaded
pseudocode for transposing an n×n matrix A in place:

```
P-TRANSPOSE (A)
n ← A.rows
parallel for j ← 2 to n
parallel for i ← 1 to j - 1
swap A[i,j],A[j,i]
```

Analyze the work, span, and parallelism of this algorithm.