Estimating Avogadro's Number

Kevin Wayne
Princeton University
wayne@princeton.edu

The assignment, as given to students.

Repeat a famous physics experiment to track the motion of particles immersed in a liquid undergoing Brownian motion; fit the data to Einstein's statistical model of molecular motion; and estimate Avogadro's number. The experiment involves the following five components:

Data collection (optional). We supply students with the raw data as sequences of 200 JPEG images.
Image segmentation. Read in an image and use thresholding to separate the image into foreground and background pixels.
Particle identification. Find maximal blobs of connected foreground pixels using depth-first search.
Particle tracking. Determine how far each particle moves between observations via a simple nearest neighbor calculation.
Data analysis. Estimate Avogadro's number by averaging a sequence of displacements and plugging the results into Einstein's equations.

No prior physics knowledge is required. This assignment is nifty because, with the aid of modern video microscopes and about 100 beautiful lines of code, students can replicate a Nobel-Prize winning experiment and estimate Avogadro's number.

Metadata

Summary	Repeat a famous physics experiment to track the motion of particles immersed in a liquid undergoing Brownian motion; fit the data to Einstein's statistical model of molecular motion; and estimate Avogadro's number. This assignment involves a fundamental programming technique (recursion), uses a core computer science concept (depth-first search), and shows an important role of computation in the natural sciences (to analyze experimental data).
Topics	Recursion, depth-first search, image processing, nearest neighbor, data analysis, science.
Audience	Early CS 2. Especially appealing to scientists and engineers. The version written here was used as a 2-week capstone final project in a CS 1 course.
Difficulty	This is an intermediate assignment, taking 1-2 weeks. The amount of code needed is remarkably small (but it's recursive, so requires care).
Dependencies	Relies on an image processing library Picture.java from Introduction to Programming in Java that enables the manipulation of individual pixels within the image. We have also implemented a Python version of this image-processing library.
Prerequisites	Students should have encountered (or be learning) recursion and depth-first search. The project requires little physics or math; however, a vague recollection of high-school physics or chemistry is helpful for context.
Strengths	Real data and real science. A nifty application of depth-first search to a real-world problem. Students are amazed that they can reproduce a Nobel-prize-wininng experiment using computation.
Weaknesses	The output is a single number. However, the modularization enables students (and instructors) to test and debug each component independenly.
Variants	Nothing is sacrosanct about depth-first search: any algorithm for computing connected component will do. There are many different ways to modify either image segmentation or particle tracking. Our modular design uses some object orientation; alternate designs with more or less OOP are possible.