Empirical Lab Repository

Title: Exploring Random Walks

Author: Grant W. Braught, Dickinson College, braught@dickinson.edu

Possible courses: CS1

Empirical Concepts Used: average, percent

Empirical Concepts Introduced: distributions, histograms, consistency, accuracy, percent error, root mean square, standard deviation

Computer Science Concepts Used: sequential execution, function calls, arguments

Summary: This assignment guides students through an exploration of random walks. Ultimately they investigate whether the expected root mean square (RMS) distance of an unconstrained random walk (country walk) is longer, shorter or the same as a corresponding random walk on a 2-d lattice (city walk). Along the way, students learn a small subset of the LOGO language (for turtle graphics) and explore the effects of averaging multiple trials on the consistency and accuracy of their results. A provided applet assists the student in this exploration by executing their turtle graphics programs and producing histograms of the results of random walk experiments.

The programming involved in this lab is minimal and is limited to writing some small turtle graphics programs. In particular, students are asked write several programs that draw prescribed figures and also to write programs that perform the random walks. Because this lab does not rely on any programming background it is ideally suited for use during the first week or two of a CS1 course. Also by using this lab early in CS1 students develop/revisit empirical tools such as average, percent error and standard deviation that can be relied upon for experiments later in the semester.

Variations: The applet provided with this lab contains two classes that form a basis for other possible assignments. The first is a Turtle class that students could be assigned to program early in an Objects First CS1 course. This class requires only simple instance data fields, arithmetic operations, a constructor and several accessor and mutator methods (no control structures are required). Students could be asked to program and test the Turtle class and then perform some or all of the exercises in this lab.

The second class is the TurtleInterpreter class. This class contains a parser and an interpreter for the turtle graphics language used by the applet. An implementation of this class would be an appropriate assignment for a programming languages course.

Links:

• Lab Handout (Language Independent)
  
  
• Instructor Materials
• Assignment Evaluation Form