Programming Assignment Checklist: Atomic Nature of Matter

Pair programming. On this assignment you are encouraged (not required) to work with a partner provided you practice pair programming. Pair programming "is a practice in which two programmers work side-by-side at one computer, continuously collaborating on the same design, algorithm, code, or test." One partner is driving (designing and typing the code) while the other is navigating (reviewing the work, identifying bugs, and asking questions). The two partners switch roles every 30-40 minutes, and on demand, brainstorm. Before pair programming, you must read the article All I really need to know about pair programming I learned in kindergarten.

You may choose a partner from the same or a different precept. You and your partner will each turn in a separate individually written readme.txt for the assignment, stating who your partner is and detailing your experience. However, only one of you should turn in the assignment (the .java files).

Frequently Asked Questions

How do I read in the .jpg files? Use our Picture.java data type, described in Section 3.1 of the textbook. To see it in action, program Threshold.java takes the name of a picture file as a command line argument, displays it on the screen, converts all pixels to a luminance value, and displays all those pixels with a luminance value ≥ 180 in white. It relies on the helper program Luminance.java (Program 3.1.3) to convert from color to luminance.

Are diagonal pixels considered adjacent? No, use only the 4 ordinal neighbors (N, E, S, and W).

For Blob.java, do I need to store the locations of all of the constituent pixels? No, it's much easier to only keep track of the statistics, either

(number of points, x-coordinate center of mass, and y-coordinate center of mass) or
(number of points, sum of x-coordinates, and sum of y-coordinates) needed to compute the center-of-mass.

Do I have to output the blobs, beads and displacements in the same order as shown on the assignment web page? No, although keeping it in the same order makes it easier to check (for both you and us).

What should I do if several of the beads in frame t+1 have the same bead in frame t as their closest bead? That happens from time to time, but don't worry about it. For our purposes, it is fine to ignore this case since the beads aren't supposed to get too close. If they do get close, there's no good way to track them anyway. Our posted solutions do not check for that rare case and we just let the same bead in frame t get paired a second time.

Why do I have to compare each bead in frame t+1 to each bead in frame t? Why can't I do it the other way around? Functionally, you could do it that way. However, there are times when the direction of comparison affects the results. So, for consistency of results, and to make it easier to check the answers, we ask everybody to do it in the same direction.

My physics is a bit rusty. Do I need to worry about converting units? No, we have provided all of the constants in SI units. The only conversion you should need to do is to convert from distances measured in pixels (the radial displacements) to distances measured in meters using the conversion factor of 0.175 × 10^-6 meters per pixel.

Will all of the frames be 640-by-480? Will all of the runs be comprised of 200 runs? Yes, yes. However, do not hardwire any of these constants into your program. Instead use picture.width() and picture.height() for the width and height, and use args.length for the number of command-line arguments.

How do I specify the 200 image names on the command line? One way is to type them all in.

% java BeadTracker run_1/frame00000.jpg run_1/frame00001.jpg run_1/frame00002.jpg ...

An easier alternative is to use the wildcard capability of your command-line. Assuming you want to use all JPEG files in the run_1 directory, you can use the following.

% java BeadTracker run_1/*.jpg

The file names get automatically expanded in alphabetical order, as desired.

Is there a way to make the toString() method format numbers in a nice way? Yes. String.format() works like System.out.printf(), but returns the resulting string instead of printing it. Here is our toString() method in Blob.

public String toString() {
    return String.format("%2d (%8.4f, %8.4f)", mass, cx, cy);
}

%2d means a 2 digit integer.
%8.4f means an 8 digit float (or double) with 4 digits to the right of the decimal.
%10.4e means a number in exponential form taking up 10 places (including the places for the decimal point and the e) with 4 digits to the right of the decimal point in the mantissa.

How long should my program take? It depends on the speed of your computer. Ours takes about 30 seconds to process a set of 200 frames.

How much memory should my program use? Ours uses less than 5m. You may be using substantially more if you have references to multiple Picture objects at the same time, or if you have more over-sized temporary arrays than you need. Pay attention to this. We will be looking at memory use when we run your code.

How accurate of an estimate should I get? You should get within 10% or so of the exact value for Avogadro's number (6.022142 × 10²³). The standard deviation of the radius of the beads is about 10%, so you shouldn't expect results more accurate than that.

Do I have to follow the API? Yes, you must follow the API and your client program may not call methods not in the API. However, you may add private methods (which are only accessible in the class in which they are declared).

Are the Power Point slides from the class available? Here they are.

Input, Output, and Testing

Testing. For testing, create main() methods in BlobFinder, BeadTracker, and Avogadro.

BlobFinder. Your BlobFinder should contain a main which takes a filename as a command line argument, and which outputs all of the blobs identified in the frame, using a luminance threshold of 180 followed by the beads returned using a minimum bead size of 25. For example,
```
% java BlobFinder run_1/frame00000.jpg
Blobs:
37 (220.0270, 122.8919)
 1 (254.0000, 223.0000)
17 (255.4118, 233.8824)
23 (265.8261, 316.4348)
36 (297.8333, 394.5000)
39 (312.3077, 215.8205)
23 (373.0000, 357.1739)
19 (390.8421, 144.8421)
31 (433.7742, 375.4839)
32 (475.5000,  44.5000)
31 (525.2903, 443.2903)
24 (591.0000, 399.5000)
35 (632.7714, 154.5714)

Beads:
37 (220.0270, 122.8919)
36 (297.8333, 394.5000)
39 (312.3077, 215.8205)
31 (433.7742, 375.4839)
32 (475.5000,  44.5000)
31 (525.2903, 443.2903)
35 (632.7714, 154.5714)
```
The assignment page shows the output from running BlobFinder with run_1/frame00001.jpg. The file beads-run_1.txt contains a list of all of the beads in each frame and was generated by a different client program using BlobFinder. For convenience it lists the reference frame for each set of beads. Again 180 and 25 were used for the threshold and minimum bead size.
BeadTracker. For reference, displacements-run_1.txt contains a list of all of the displacements (again using a luminance threshold of 180 and a minimum bead size of 25); it was obtained by running
```
% java BeadTracker run_1/*.jpg
 7.183
 4.793
 2.169
 5.529
 5.429
 4.396
...
```

Avogadro. For reference, the estimate of Avogadro's number using the data from run_1 is 6.6 × 10⁺²³. Here are our outputs using run_1 and run_2.

% java BeadTracker run_1/*.jpg | java Avogadro
Boltzmann = 1.254e-23
Avogadro  = 6.633e+23

% java BeadTracker run_2/*.jpg | java Avogadro
Boltzmann = 1.420e-23
Avogadro  = 5.855e+23

Submission

Use the following readme file template.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

Download the directory atomic to your system. It contains the data files, Picture.java, and StdIn.java. Each directory run_[1-9] contains a sequence of 200 JPEG images. In total, these data files consume 70MB of space.

Blob data type. Implement the Blob data type. If you think carefully, you do not need to store all of the individual pixels that comprise a blob - three numeric fields should suffice. Be sure to thoroughly test your data type before proceeding.
BlobFinder data type. Implement the BlobFinder data type. This is the most difficult part.
- Review Section 2.4 in the textbook, especially the part on depth-first search. Finding all the pixels in a blob is similar to finding a percolating path.
- The crux of this part is to write a recursive method dfs(int i, int j) that locates all of the foreground pixels in the same blob as the foreground pixel (i, j). To do, this use depth-first search: mark (i, j) as in the current blob, then recursively mark all of its foreground neighbors as in the current blob (but don't recur if the pixel has previously been marked or the pixel indices are out-of-bounds).
- Now, implement a nonrecursive method private findBlobs() that runs dfs(i, j) from each unmarked pixel (i, j). All of the pixels you encounter by calling dfs(i, j) are in one blob.
- Write the method show() to print out all the blobs.
- Implement a main() method that takes the name of a JPEG file as a command line parameter and prints out all of the blobs. The threshold should be set as a named constant in the main() method.
- Next, implement the method public getBeads() that searches through the blobs and stores all of the beads (blobs of sufficient size) in a Blob array that is exactly the right size for all of the beads.
- Add a section to your main() method so that now it prints out the beads after it prints out the blobs. The minimum bead size should be set as a named constant in the main() method.
BeadTracker client. The main() method in BeadTracker takes an arbitrary number of command line parameters, args[0], args[1], and so forth. You only need to consider two frames at a time, so don't try to store them all in memory at one time.
Avogadro client. The main() method in Avogadro reads a sequence of real numbers from standard input and prints out the estimate of Avogadro's number using the formulas provided in the assignment. To calculate σ², use the second formula listed with radial displacements; these are the results from BeadTracker. To test your program, use the file displacements-run_1.txt.
```
% java Avogadro < displacements-run_1.txt
Boltzmann = 1.254e-23
Avogadro  = 6.633e+23
```

Enrichment

What is polystyrene? It's an inexpensive plastic that is used in many everyday things including plastic forks, drinking cups, and the case of your desktop computer. Styrofoam is a popular brand of polystyrene foam. Computational biologists use micron size polystyrene beads (aka microspheres, latex beads) to "capture" a single DNA molecule, e.g., for a DNA test.

What's the history of measuring Avogadro's number? In 1811, Avogadro hypothesized that the number of molecules in a liter of gas at a given temperature and pressure is the same for all gases. Unfortunately, he was never able to determine this number that would later be named after him. Johann Josef Loschmidt, an Austrian physicist, gave the first estimate for this number using the kinetic gas theory. In some places, this number is known as Loschmidt's number. In 1873 Maxwell estimated the number of be around 4.3 × 10²³; later Kelvin estimated it to be around 5 × 10²³. Perrin gave the first "accurate" estimate (6.5 - 6.8 × 10²³) of, what he coined, Avogadro's number. Here's a reference on estimating Avogadro's number. The most accurate estimates for Avogradro's number and Boltzmann's constant are computed using x-ray crystallography: Avogadro's number is approximately 6.022142 × 10²³; Boltzmann's constant is approximately 1.3806503 × 10^-23 J K^-1.

Where can I learn more about Brownian motion? Here's the Wikipedia entry. You can learn about the theory in ORF 309 - it's likely the first subject you'll be asked about if you interview on Wall Street.

Intro to Computer Science
wayne@cs.princeton.edu