Random Writer

Joe Zachary
School of Computing
University of Utah
February 19, 2003

This nifty assignment is based on an idea advanced by Claude Shannon in 1948 [3] and subsequently popularized by A.K. Dewdney in his column in Scientific American in 1990 [1].

I have used this assignment with great success in my CS 2 classes. The assignment is nifty for at least three reasons.

  1. When the problem is first presented to the students, it sounds extremely difficult. However, when they understand the algorithm that I have in mind, they are impressed with how straightforward it is.

  2. When the students complete the Random Writer they have a lot of fun playing with it. I always run a contest to see who can generate the funniest output.

  3. The Random Writer is not a toy program; it can process the text of entire books.

The assignment touches on file input/output, string searching, the use of a dynamic linear structure (such as Java ArrayLists), and the use of randomly-generated integers. When assigned in Java, the students need to understand the portions of the Java API (java.lang.String, java.lang.StringBuffer, java.util.Random, java.util.ArrayList, java.io.FileReader, and java.io.FileWriter) that it exploits. The assignment typically takes one week.

One of the students who completed the assignment the first time I gave it used the idea behind the Random Writer to devise a new technique for synthesizing texture patterns in computer graphics applications [2]. Rather than growing a text string one character at a time, he grows texture patterns one pixel at a time.

References

[1] A.K. Dewdney. A potpourri of programmed prose and prosody. Scientific American, 122-TK, June 1989.

[2] A.A. Efros and T.K. Leung. Texture synthesis by non-parametric sampling. IEEE International Conference on Computer Vision, September 1999.

[3] C.E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27, 1948.


Extra info about this assignment: