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:
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).
Recursion, depth-first search, image processing, nearest neighbor, data analysis, science.
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.
This is an intermediate assignment, taking 1-2 weeks. The amount of code needed is remarkably small (but it's recursive, so requires care).
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.
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.
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.
The output is a single number. However, the modularization enables students (and instructors) to test and debug each component independenly.
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.