ForkJoin Framework Exercises

As in previous assignments, we'll be using GitHub Classroom to create a repository. The key difference is that this is a pair assignment, so we're going to bravely enter the wild west of GitHub Classroom teams and use its capability to create a shared repository that both you and your project partner have access to. Here's how it works (fingers crossed). My strong recommendation is that you do this together, sitting side-by-side, at two separate computers.

1. One of you (and only one of you) should visit this GitHub classroom link (which I've now placed in Moodle). Log into GitHub if necessary. You should be taken to a screen that invites you to either "Join an existing team" or to "Create a new team". You should create a new team. Please name the team with your GitHub usernames. For example, if users StevieP and FSchiller are working together, please name the repository StevieP-FSchiller. The order doesn't matter. This will make it easier for the graders to know who the repositories belong to. That said, please do not put your names in your code itself. We will be obscuring the repository names when grading so we can do so anonymously; that's harder to automate if you put your names in program comments. (If you are working alone, just use your name.) GitHub should then hopefully respond with a screen that says "You are ready to go!" and supplies you with a link for the repository that you are creating. Click on that link, and you should be taken to the repository. If you've gotten this far, you have successfully created the repository, and you (the user who is logged in) have access to it. (If you are working alone on the project, you can stop here.)
2. The other one of you, after the above is complete, should use a different browser (preferrably on a different computer) to visit the same GitHub classroom link. You'll see the screen asking you to "Join an existing team" or to "Create a new team." You should be able to see the team that your partner created above; click the "Join" button. This should then take you to the "You are ready to go!" screen, and you can hopefully find a link to the repository. Click on it.

Congrats! If the above worked, you should both have access to a shared repository. If not, ask for help.

Note again that my expectation is that you are engaged in pair programming, and thus you are working together on a single computer. It is likely that you'll be happiest cloning this repository once to one of your local computers (or a lab account), and working together from there. However, as long as you are regularly committing and pushing your code in progress, you'll both have access to seeing it.

As in previous projects, clone the project, then take a look at it. I've provided SumForkJoin as an example, and so SumForkJoinTest should run successfully. You can also look at this Oracle tutorial on Fork/Join for another example.

(This may sound familiar…) Fill in MaxForkJoin.java so that it will calculate the maximum sine value of every value in an array using the ForkJoin framework. You may assume the array has at least one element. You should use a sequential cutoff (e.g. 10), below which no more recursive tasks are forked. When complete, the tests in MaxForkJoinTest should pass. That said, these tests are not comprehensive. Read through the tests, understand what it's doing, and think about if you need to test anything else.

Consider the problem of finding the longest sequence of some number in an array of numbers: longestSequence(i, arr) returns the longest number of consecutive i in arr. For example, if arr is {2, 17, 17, 8, 17, 17, 17, 0, 17, 1} then longestSequence(17, arr) is 3 and longestSequence(9, arr) is 0. Fill in the code for LongestSequenceForkJoin.java that implements longestSequence using the ForkJoin framework. You should again use a sequential cutoff, but set it via a variable so that it can be easily changed. We may test your code with a variety of cutoff values, including 1.

You may find that combining two subproblems back together is trickier here than it was for the previous exercises. In the case of sum, we were able to just sum the answers from the left and right side. Here, you have to worry about the challenging possibility that the longest sequence was in the middle of the array, and that you split it when dividing the problem into two halves. There are undoubtedly many approaches to handling this.

Hint: my approach was to not return an integer as the answer from each RecursiveTask, but rather to return an object such as the below:

class Result {
  int numLeftEdge;
  int numRightEdge;
  int numLongest;
  // ... other info if you think you need it
}

For example, numLeftEdge should represent the length of the sequence at the beginning of the range processed by a subproblem. Think carefully about how to combine results.

Follow the instructions in the intro assignment on how to push your work to GitHub, making sure to use a commit comment of "finished" to indicate that you're done. When done, visit GitHub, find your repository, and verify that your code was submitted as you intended.

This assignment was originally created by Laura Effinger-Dean; Dave Musicant has made substantial revisions.