COS 126

The Atomic Nature of Matter 		Programming Assignment Checklist

Assignment Page

Frequently Asked Questions (general)

Do I need to follow the prescribed APIs? Yes, we will be testing the methods in an 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 an API; you may, however, add private methods (which are accessible only in the class in which they are declared).

Am I allowed to use Java's built-in packages? No. This assignment is intended as a capstone project, requiring you to combine programming techniques that you learned during the class. There is no need to use any of the libraries in java.util.

My answers match the reference answers, except sometimes they are off by 0.0001. Why could cause this? It is likely a combination of floating-point roundoff error and printing only 4 digits after the decimal point. For example, this discrepancy can arise if one solution computes the value 0.12345 (which gets rounded up to 0.1235) and another computes the value 0.1234499999999 (which gets rounded down to 0.1234). You need not worry about such discrepancies on this assignment.

Are the PowerPoint slides from precept available? Yes, in pdf or in ppt.

Frequently Asked Questions (Blob)

How can I implement the toString() method to format the numbers? Use String.format(). It works like StdOut.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 pp. 130–132 of the textbook to learn more about formatted printing.

Which value should distanceTo() return if the mass of one or both blobs is zero? We recommend Double.NaN. Since this corner case is not specified in the API, we won't test it.

What should toString() return if the mass is zero? We recommend "0 (NaN, NaN)". Since this corner case is not specified in the API, we won't test it.

Frequently Asked Questions (BeadFinder)

How should I read a JPEG file? Use the Picture data type.

How do I compute the luminance of a pixel? First, get the Color of that pixel. Then, use the appropriate method in Luminance.java (Program 3.1.3) to get the luminance value for that color.

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

Must I print the beads and displacements in the same order as shown in the assignment specification? No, the order is not specified.

How can I specify the name of a subdirectory in Windows? Use the backslash character (\) instead of the forward slash character (/).

Can I execute my program from within DrJava? No, use either Terminal or Command Prompt. DrJava does not support using wildcards such as *.jpg. DrJava also requires that you escape each \ character.

Frequently Asked Questions (BeadTracker)

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 only rarely, so you should not worry about it—just let the 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?

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, but one that you must follow because it is prescribed in the assignment specification.

Frequently Asked Questions (Avogadro)

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 × 1023). The standard deviation of the radius of the beads is about 10%, so you shouldn't expect results more accurate than this. Your output, however, should agree exactly with ours.

My physics is a bit rusty. Do I need to worry about converting units? Not much, since all of the constants are 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, by using the conversion factor of 0.175 × 10−6 meters per pixel.

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

Checkstyle complains about the variables I named T and R. Which names should I use instead? A constant variable (a variable whose value does not change during the execution of a program, or from one execution of the program to the next) should begin with an uppercase letter and use underscores to separate any word boundaries, such as GRAVITATIONAL_CONSTANT. Constant variables should have more meaningful names, such as TEMPERATURE or GAS_CONSTANT.

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

% java-introcs 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-introcs BeadTracker 25 180.0 25.0 run_1/*.jpg

Frequently Asked Questions (performance analysis)

How can I estimate the running time of my BeadTracker program? Use the Stopwatch data type from Section 4.1. Remember to remove it and any additional print statements from your submitted version of BeadTracker.java. 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 can I run BeadTracker with a variety of input sizes? Don't all the runs have 200 frames? They do, but when you are performing timing experiments, you can simply use a subset of them. On OS X, you can use the wildcard capability of the command-line to run 10 frames, 20 frames, 40 frames, 80 frames, and 160 frames, as follows: 

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

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

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

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

% java-introcs 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-introcs BeadTracker 25 180.0 25.0 run_1\frame000*.jpg      > temp.txt

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

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

How long should BeadTracker take? It depends on the speed of your computer, but processing 200 frames should take around 10 seconds or less.

How much memory should my program use? Our program 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-introcs -Xmx5m BeadTracker 25 180.0 25.0 run_1/*.jpg

When I test with a very small luminance threshold, I get a StackOverflowError, but my code works for larger luminance thresholds. What does this mean? Since DFS is recursive, it consumes memory proportional to the height of the function-call tree. If the luminance threshold is small, the blobs can be very big, and the height of the function-call tree may be very large. We won't test your program on inputs with such big blobs. If, however, you are determined to get it to work on such cases, use the command-line option -Xss20m to increase the stack space. 

% java-introcs -Xss20m BeadTracker 25 18.0 25.0 run_1/*.jpg

Input, Output, and Testing

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

Possible Progress Steps

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

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 (also known as microspheres and 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 × 1023; later Kelvin estimated it to be around 5 × 1023. Perrin gave the first "accurate" estimate (6.5–6.8 × 1023) 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 × 1023; Boltzmann's constant is approximately 1.3806503 × 10−23.

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