# Parallelism

## Table of contents

Pull the `skeleton`

repository to get the `para`

assignment. Commit and push your changes to GitLab before submitting your homework to Gradescope.

- Note
- There is no autograder for this assignment. Make sure that your implementation is correctly parallelized; it can pass the tests even if there is no parallelism.

## Longest sequence

Use the fork/join framework to implement `getLongestSequence`

. Given an `int val`

, `int[] arr`

, and an `int sequentialCutoff`

, `getLongestSequence`

returns the length of the longest consecutive sequence of `val`

in `arr`

.

For example, if arr is `[2, 17, 17, 8, 17, 17, 17, 0, 17, 1]`

, then `getLongestSequence(17, arr)`

should return 3 and `getLongestSequence(35, arr)`

should return 0.

Your code must have O(N) work, O(log N) span, where N is the length of `arr`

, and use the `sequentialCutoff`

argument. You may use the `SequenceRange`

class to carry the return value.

## Multi-pass filtering

Use the fork/join framework to implement `filterEmpty`

. Given a `String[] arr`

, `filterEmpty`

returns an array with the lengths of the non-empty strings in `arr`

in order.

For example, if arr is `["", "", "cse", "332", "", "hw", "", "7", "rox"]`

, then `filterEmpty(arr)`

should return `[3, 3, 2, 1, 3]`

.

A parallel algorithm for solving this problem in O(N) work and O(log N) span is as follows.

- Parallel map to produce a bit set.
- Parallel prefix over the bit set. (Implementation provided in the skeleton.)
- Parallel map to produce the output.

Do not bother with a sequential cutoff for this exercise. Your base case may process a single element.