Divide And Conquer Nucleobase Count Assignment

Motivation

Gain experience with forking parallel tasks in a recursive, divide-and-conquer approach.

Building On Previous Exercises

Be sure to complete the Half & Half exercise first.

Code To Invesigate

• IntPredicate
  • test(value)

Code To Implement

GreaterThanThreshold

class:	GreaterThanThreshold.java
methods:	constructor threshold test
package:	threshold.exercise
source folder:	student/src/main/java

constructor

method: public GreaterThanThreshold(int threshold) (sequential implementation only)

The threshold value passed to the constructor is critical to the correct operation of instances of GreaterThanThreshold. Be sure to hang onto the value in a field. This field need never change, so the field you declare should be final. It should not be directly accessed so the field should be declared private.

threshold

method: public int threshold() (sequential implementation only)

Return the threshold value this instance was constructed with.

test

method: public boolean test(int value) (sequential implementation only)

In order to complete the contract of implementing IntPredicate, GreaterThanThreshold must implement the test(value) method. Return true if the value passed to the test method is strictly greater than the threshold the current instance was constructed with.

DivideAndConquerNucleobaseCounter

class:	DivideAndConquerNucleobaseCounter.java
methods:	constructor isParallelPredicate countRangeKernel count
package:	count.exercise
source folder:	student/src/main/java

Much like the previous implementations of NucleobaseCounter, we will be creating one which solves the problem in a divide-and-conquer style.

Computation Graph

The computation graph below depicts sorting an array of length 64 with a predicate which returns true if the range length is > 10.

constructor

constructor: public DivideAndConquerNucleobaseCounter(IntPredicate isParallelPredicate)

Hang onto isParallelPredicate to test if a current [min, maxExclusive) length warrants parallelism.

isParallelPredicate

method: public IntPredicate isParallelPredicate() (sequential implementation only)

Simply return the value of the parameter passed to the constructor.

countRangeKernel

method: private int countRangeKernel(byte[] chromosome, Nucleobase targetNucleobase, int min, int maxExclusive) (parallel implementation required)

Warning: Do NOT use NucleobaseUtils.countRange() if IntPredicate.test(length) returns true

This helper method first uses the predicate to test whether the length of [min, maxExclusive) warrants parallelism.

If the predicate's test passes, divide [min, maxExclusive) into two halves and recursively count them in parallel.

If not, fall back to sequentially counting with NucleobaseUtils.countRange(chromosome, targetNucleobase, min, maxExclusive).

count

method: public int count(byte[] chromosome, Nucleobase targetNucleobase) (sequential implementation only)

Simply invoke the helper method, specifying the min and maxExclusive to count the entire array.

Correctness

class:	_GreaterThanThresholdTestSuite.java
package:	threshold.exercise
source folder:	testing/src/test/java

class:	_DivideAndConquerNucleobaseCounterTestSuite.java
package:	count.exercise
source folder:	testing/src/test/java

Pledge, Acknowledgments, Citations

file:

nucleobase-count-dnc-pledge-acknowledgments-citations.txt

More info about the Honor Pledge