Programming Assignment Checklist: Atomic Nature of Matter

Pair programming. On this assignment, just like the previous assignments, you are encouraged (not required) to work with a partner provided you practice pair programming (same rules as last assignment).

Frequently Asked Questions

Do I need to follow the prescribed API? Yes, we will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points. You may not add public methods to the API; however, you may add private methods (which are only accessible in the class in which they are declared).

Are the PowerPoint slides from precept available? Here they are.

How do I read in the .jpg files? Re-read the Picture API, which is available in the cheatsheet section of the booksite. 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).

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 for you (and us) to check. However, you must follow the instructions for the BlobFinder.main() which says to print out the list of beads with size at least P before printing out the list of all the blobs.

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.

I am able to find beads and blobs correctly, but my BeadTracker gives a few errors, despite that it is mostly working. Why could this be? Make sure you exactly follow the given instructions: for each bead in each frame, you should be finding the closest bead to it in the previous frame. Doing the reverse gives slightly different results. (See also the next question.)

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? It's an arbitrary choice. We require you do it this way to make it easier to check your answer.

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.

Can I assume that all of the frames be 640-by-480 and that all of the runs will consist of 200 frames? No, do not hardwire any of these constants into your program. Use picture.width() and picture.height() for the width and height, and use args.length for the number of command-line arguments.

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);
}

See p. 125 of the textbook to learn more about formatted printing.

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

% java BeadTracker 25 180.0 25.0 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: for example, the following specifies (in alphabetical order) all .jpg files in the run_1 directory.

% java BeadTracker 25 180.0 25.0 run_1/*.jpg

How can I estimate the running time of my BeadTracker program? Use the Stopwatch object from Section 4.1. Remember to remove it and any additional print statements from your submitted version of BeadTracker.java. Alternatively, you may use the command-line switch java -Xprof BeadTracker (usually the flat profile is the most appropriate). Either way, when you execute BeadTracker, redirect the output to a file to avoid measuring the time to print the output to the terminal. Run BeadTracker with a variety of input sizes which allow you to get good timing data and form a doubling hypothesis.

How do I run BeadTracker with a variety of input sizes? Don't all the runs have 200 frames? They do, but when you are investigating the timing, you don't care about the actual displacements, only how long it takes to compute them.

On OS X or Linux, you can use the wildcard capability of the command-line to run 10 frames, 20 frames, 40 frames, 80 frames, and 160 frames:

% java BeadTracker 25 180.0 25.0 run_1/frame000[0]*.jpg    > temp.txt

% java BeadTracker 25 180.0 25.0 run_1/frame000[0-1]*.jpg  > temp.txt

% java BeadTracker 25 180.0 25.0 run_1/frame000[0-3]*.jpg  > temp.txt

% java BeadTracker 25 180.0 25.0 run_1/frame000[0-7]*.jpg  > temp.txt

% java BeadTracker 25 180.0 25.0 run_1/frame000*.jpg run_1/frame001[0-5]*.jpg > temp.txt

On Windows, one simple way is to create several subdirectories with the desired number of frames. Another way is to use the limited wildcard capability of command prompt to run 100, 200 and 400 frames.

> java BeadTracker 25 180.0 25.0 run_1\frame000*.jpg      > temp.txt

> java BeadTracker 25 180.0 25.0 run_1\*.jpg              > temp.txt

> java BeadTracker 25 180.0 25.0 run_1\*.jpg run_1\*.jpg  > temp.txt

How long should my program take? It depends on the speed of your computer, but probably between a few seconds and 30 seconds for 200 frames.

How much memory should my program use? Ours uses less than 5 MB. You will receive a deduction if you use substantially more. The most common way to waste memory is to hold references to an array of Picture objects in BeadTracker instead of only two at a time. You can use the -Xmx option to limit how much memory Java uses: for example, the following command limits the memory available to Java to 5 MB.

% java -Xmx5m BeadTracker 25 180.0 25.0 run_1/*.jpg

When I test with very small luminance, I get a StackOverflowError, but my code works for larger luminance. What does this mean? Since DFS is recursive, it takes up memory proportional to the height of the recursive call tree. If the luminance is small, the blobs can be very big, and the call tree height may be very large. We won't test it on cases with such big blobs. But if you are really interested in getting it to work when testing at home, try using the command-line option java -Xss20m to increase the stack space.

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 this.

However, your estimates for a given run should agree exactly with ours. Our output from Avogadro for run_1 is given on the assignment page. Our output from Avogadro for run_2 is given below in the Testing section. Here is our output from run_6.

% java BeadTracker 25 180.0 25.0 run_6/*.jpg | java Avogadro
Boltzmann = 1.3482e-23
Avogadro  = 6.1670e+23

Why is it recommended to not use DrJava to run the code? DrJava does not support using wildcards like *.jpg and also requires that you escape each \.

Input, Output, and Testing

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

BlobFinder. The assignment page shows the output from running BlobFinder with run_1/frame00001.jpg. Here are the results for run_1/frame00000.jpg:

% java BlobFinder 25 180.0 run_1/frame00000.jpg
7 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)

13 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)

The file beads-run_1.txt lists all of the beads in each frame (using tau = 180.0 and P = 25). and was generated by a different client program using BlobFinder: for convenience it lists the reference frame for each set of beads.

BeadTracker. For reference, displacements-run_1.txt and displacements-run_2.txt contain a list of all of the displacements (using tau = 180.0 and P = 25) for run_1 and run_2, respectively. They were obtained by running

% java BeadTracker 25 180.0 25.0 run_1/*.jpg   % java BeadTracker 25 180.0 25.0 run_2/*.jpg
 7.1833                                        5.1818
 4.7932                                        7.6884
 2.1693                                        6.7860
 5.5287                                        6.4907
 5.4292                                        4.2102
 4.3962                                        1.1412
 ...                                           4.4724
                                               7.5191
                                               3.0659
                                               4.4238
                                               5.0600
                                               1.7280
                                               ...

Avogadro. The assignments gives the output for run_1. Below is the output for run_2.

% java BeadTracker 25 180.0 25.0 run_2/*.jpg | java Avogadro
Boltzmann = 1.4200e-23
Avogadro  = 5.8552e+23

Possible Progress Steps

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

Download the files from the assignment page using the .zip or FTP, as in previous weeks. It contains the data files and Luminance.java. Each directory run_[1-9] contains a sequence of 200 JPEG images. In total, these data files consume 70MB of space. The file beads-run_1.txt lists the beads found in each frame of run_1 using tau = 180.0 and P = 25. The files displacements-run_1.txt and displacements-run_2.txt are the output of BeadTracker for those runs.
Blob data type. Implement the Blob data type. You do not need to store all of the individual pixels that comprise a blob; instead, store three numbers:
- (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.
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 private nonrecursive helper method 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.
- Next, implement the method countBeads() that counts the number of beads (blobs of sufficient size).
- Implement a main() method that takes as command-line arguments P, tau, and the name of a JPEG file. The main() method should print out the number of blobs and the number of beads with at least P pixels.
- Next, implement the method getBeads() that searches through the blobs and stores all of the beads (blobs of sufficient size) in a Blob array. The length of the array should be equal to the number of beads.
- Modify main() to print out the beads and blobs.
BeadTracker client. The main() method in BeadTracker takes an arbitrary number of command-line arguments, 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.

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 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 Avogadro'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.