CS 161 Assignment #9 CS 161 Assignment #9 Due Wednesday, May 4th by 11:59pm (Not accepted late!) Partners You are welcome to work in groups of two on this assignment if you want. If you choose to work with a partner, please send me a note so I know who's working with whom. Only one member of the team should submit the assignment, but make sure both names are in the comment at the top of the classes. Both partners should contribute equally to the effort, and neither should start without first having an initial planning meeting to discuss an implementation plan. Introduction: For your final assignment, you'll build an application that can determine which subjects in a large group have tested positive for Covid 19, without having to test each subject individually. In addition to giving you more practice with your basic Java skills, this project will give you a chance to write a complete application (one with a main method), and one that takes input from both the keyboard and a file. There's a long history of using pooled testing to detect viruses and other pathogens. For example, when you donate blood, a portion of your donation is combined with other donors' blood, and the entire "pool" is tested for things like HIV. If any subject in the group has HIV, the pool will test positive. We wouldn't know which subject had HIV unless we then tested each subject individually, but in situations where infections are rare this can still be an efficient way to screen subjects. As Covid started spreading in the spring, an Israeli research team reported an approach to pooled testing that uses techniques from computer science to improve the efficiency: Subjects' samples are added to multiple pools, but arranged carefully so that we can deduce which subjects tested positive without having to test each individually. In one of their examples, they were able to evaluate 384 subjects with only 48 tests! Let's work through a scaled-down example. The diagram below shows eight subjects (0–7) and six different pools, labelled A through F. You can see that subject 2, for example, is in pools A, D, and E, meaning that their sample swab was split across those three groups and combined with samples from the other subjects in each pool. Assume that subject 5 is Covid positive. That would lead pools B, D, and E (shown in red below) to test positive. We can tell that subject 5 is responsible for these positive tests though, since every pool containing 5 has tested positive. Subject 4 is in several of those pools as well, but is also in pool C, which tested negative. We'll take that as evidence that subject 4 isn't responsible for the positive results. (The results for pool C could have been a false negative, but we'll assume for this assignment that the tests are 100% accurate. It would be an interesting extension to think about how to handle false positives or negatives though.) The savings in this example weren't very dramatic. We determined the status of 8 subjects with 6 tests. That's still better than having to do 8 tests, but the process gets more efficient as it scales up to larger numbers of subjects. What if several subjects test positive? Will this still work? Imagine that subjects 0 and 5 are both positive. The diagram below shows all of the pools containing 0 and 5 in red — those groups would all test positive. The good news is that we would still be able to determine that 0 and 5 are positive — every group they're in tested positive. (Note that 5 is not in every positive group, but every group it's in tested positive. Same for 0.) Unfortunately, that's also true for subjects 2 and 4, so we'd mistakenly conclude that they're Covid positive as well. That can happen if the number of positive subjects is large with respect to the pool size, so this approach works best for fairly low positivity rates. Deducing Which Subjects are Positive We'll start by assuming that the subjects in all of the positive groups are positive, then look for evidence that some of those subjects are actually negative and eliminate them. For example, in the example above where groups B, D, and E test positive, we would start by considering everyone in those groups to be positive. If we created a new pool containing all of those subjects, it would hold 4, 5, 6, 1, 7, 0, and 2 — everybody except 3! (Note that we want to avoid duplicates when merging the positive pools.) Next we'd inspect the negative pools to see if any of our guilty suspects were actually innocent. When we consider pool A, for example, we find that 0, 2, 3, and 7 must actually be Covid negative — if any of them were positive, that whole group would've tested positive. We can therefore remove 0, 2, and 7 from our group of suspects. That just leaves 4, 5, 6, and 1. Considering pool C would remove 4 and 1 from our group of suspects, leaving 5 and 6. Pool F would exonerate subject 6. That only leaves 5 in our positive group when we're done with our analysis. Project Overview We'll write a program consisting of the three classes shown below. (Starter code is in the PooledTesting.zip project.) The Pool class represents a group of subjects. It records whether the group has tested positive or not, as well as the ID numbers of the subjects in the pool. The class also contains methods for merging pools and doing other manipulations that will help determine which individual subjects are positive. The PoolProcessor class contains code that reads information from a file, creates the Pools, consults the user for information about which pools have tested positive, then does the computations to figure out which subjects should be considered positive. The PooledSampleTester class creates a PoolProcessor object and starts things running. Documentation for all three classes is here. I'm giving you all of the code in PooledSampleTester, and at least an outline of the other two. The data files are organized as shown below. The first line contains the column labels, separated by a tab character. The remaining lines consist of a pool label (a String) and a subject ID (an int) to be added to the specified pool, separated by a tab. The sample data file below describes the six pools in the introduction above. Here, each pool's entries are consecutive (all of A's subjects come before B's, etc), but you shouldn't assume they'll always be that way. Your code should still work regardless of the order of the lines in the input file. The BlueJ project folder contains this file, pooling_example.txt, as well as a much larger file, pooling384_48_by_pool.txt, containing pool assignments for 384 subjects. (BlueJ doesn't display these files, but they're in the project folder.)
pool subject
A 0
A 2
A 3
A 7
B 4
B 5
B 6
B 1
C 0
C 3
C 4
C 1
D 5
D 6
D 7
D 2
E 0
E 4
E 5
E 2
F 6
F 7
F 1
F 3
Specifics The Pool Class The Pool class uses an ArrayList to record the ID numbers of the subjects in the pool, and keeps a boolean field showing whether this pool has tested positive or not. (The Pool class doesn't decide this on its own — the PoolProcessor class will set it as appropriate.) There are methods for setting and checking the test status, and for adding new subjects to the pool (assuming they're not already present), as well as a toString method. The output from your toString method should match that shown in the testing section below exactly. The merge method takes a reference to another pool and adds its contents to our own (again, being careful to avoid duplicates). This will come in handy when we try to combine all of the positive pools into one big pool. The eliminate method helps whittle down the group of potentially positive subjects. It takes a reference to another pool and, if we're positive and they're negative, removes subjects from our pool that appear in the other pool. The PoolProcessor Class The PoolProcessor class keeps an ArrayList of Pools, and a corresponding ArrayList of their names (labels). Its constructor reads a data file, creates all of the pools, and fills them with subjects. The detect method takes a list of test results (the names of the pools that tested positive), and implements the algorithm above for deducing which subjects must be positive. I'm giving you a "to-do list" for each method to get you started. Output from these methods should match that shown in the testing section below as well. The PooledSampleTester Class The PooledSampleTester class has a main method that starts the program running. It creates a PoolProcessor object, passing the constructor the name of the file to read. After prompting the user to enter the names of the pools that should be considered positive, it runs the detect method to determine which subjects have tested positive. It's currently set up to read from the small sample file. You'll want to edit the top of the file to use the larger test file when making sure your program works, but otherwise you won't need to change anything in this class. Testing You should test your Pool class by itself before testing PoolProcessor. Below, I'm showing codepad interactions with Pool demonstrating how it should work. Three pools are created — b, d, and f — that correspond to the pools of the same name at the top of this assignment page. These interactions show how calls to setTestResults change the status on the pool, and how toString represents a pool. Pool d is merged into pool b, creating one large pool of potentially positive subjects. The negative pool f is then used to eliminate some of those subjects from the pool, as it proves that some of them were actually Covid negative.
Pool b = new Pool(); // Make pool b hold 4,5,6,1
b.setTestResults(true);
b.addSubject(4);
b.addSubject(5);
b.addSubject(6);
b.addSubject(1);
b.toString()
"pos(4, 5, 6, 1)" (String)
Pool d = new Pool(); // Make pool d hold 5,6,7,2
d.setTestResults(true);
d.addSubject(5);
d.addSubject(6);
d.addSubject(7);
d.addSubject(2);
d.toString()
"pos(5, 6, 7, 2)" (String)
b.merge(d); // Merge d into b (w/o duplicates)
b.toString()
"pos(4, 5, 6, 1, 7, 2)" (String)
Pool f = new Pool(); // Make negative pool
f.addSubject(6);
f.addSubject(7);
f.addSubject(1);
f.addSubject(3);
f.toString()
"neg(6, 7, 1, 3)" (String)
b.eliminate(f); // Removes 6,7,1 from b
b.toString()
"pos(4, 5, 2)" (String)
Once Pool is working, try testing PoolProcessor. Below I'm showing codepad interactions in which a PoolProcessor object is created, and asked to read the file "pooling_example.txt". (Output that would appear in the terminal window is shown indented below.) The constructor printed out the details of the pools it created, as well as the total number of subjects read and pools created. I then made a list of strings containing "B", "D", and "E" — three pools I decided had tested positive. This list was passed to detect, and it deduced that based on those test results for the pools, only subject 5 was actually Covid positive. (The detect method printed the pool when it was done.)
PoolProcessor pp = new PoolProcessor("pooling_example.txt");
Read 24 subjects and 6 pools:
A: neg(0, 2, 3, 7)
B: neg(4, 5, 6, 1)
C: neg(0, 3, 4, 1)
D: neg(5, 6, 7, 2)
E: neg(0, 4, 5, 2)
F: neg(6, 7, 1, 3)
import java.util.ArrayList;
ArrayList testResults = new ArrayList(); testResults.add("B"); testResults.add("D"); testResults.add("E"); pp.detect(testResults); Positive subjects: pos(5) You should also test your program by running the main method in PooledSampleTester. It will automate some of the steps shown above. Test it with a variety of scenarios, and make sure it properly picks the Covid-positive subjects. Style Guide Before you submit your assignment, go through the checklist below and make sure your code conforms to the style guide. No unused variables or commented-out code is left in the class Instance variables only used when absolutely necessary Javadoc comment above each class, and class comment at the top of each class All methods have Javadoc comments. These should now include @param tags for all inputs and @return tags for returned values. Inline comments used to explain how sections of code work, as appropriate Numbers have been replaced with constants as appropriate (i.e. no "magic numbers") Proper capitalization of variables, methods, and classes Use white space to separate different sections of your code Once you've tested your code and verified that it meets style guidelines, submit from within BlueJ as usual. Grading This assignment will be graded out of a total of 120 points: [5] Pool constructor [10] setTestResults() and isPositive() in Pool class [10] addSubject() in Pool class [15] eliminate() in Pool class [10] merge() in Pool class [15] toString() in Pool class [25] PoolProcessor constructor [25] detect() method in PoolProcessor [5] Style and commenting Submitting Before submitting, make sure you've added your name to the comment at the top of the class files, and written comments for each method. Test your methods thoroughly. When you're convinced it's ready to go, submit the project via Canvas just like you have in the past. David Chiu & Brad Richards, 2022
