CSC 321: Data Structures
Fall 2016

HW2: Queues & Music

This assignment is inispired by a Nifty Assignment introduced by Kevin Wayne (Princeton University) and refined by Stuart Reges (University of Washington).

It is to be completed individually by each student, with no help from anyone other than the instructor.


When a piano wire is struck, the wire vibrates and creates sound. The vibration can be measured by sampling the displacement of the wire at equally spaced points. These displacement measurements can be stored digitally, say in a list or queue structure, then used to recreate the sound wave over a speaker.

Sample Displacements

For this assignment, you will store the displacement values for a piano wire in a queue structure. When at rest, the wire can contain energy at any frequency. This is modeled by assigning the queue to contain random real numbers between -1/2 and +1/2. After the wire is struck, it vibrates causing a displacement that spreads wave-like over time. The Karplus-Strong algorithm simulates this vibration using a fairly simple update process: it repeatedly adds to the end of the queue the average of the first two samples, scaled by an energy decay factor of 0.996, and removes the first sample from the queue.

Karplus-Strong algorithm

This simple algorithm provides an effective model of the wire vibration due to two features: the queue feedback mechanism and the averaging operation.

  1. The queue feedback mechanism. The queue models the medium (a wire fixed at both ends) in which the energy travels back and forth. The length of the queue determines the fundamental frequency of the resulting sound. Sonically, the feedback mechanism reinforces only the fundamental frequency and its harmonics (frequencies at integer multiples of the fundamental). The energy decay factor (.996 in this case) models the slight dissipation in energy as the wave makes a roundtrip through the wire.
  2. The averaging operation. The averaging operation serves as a gentle low pass filter (which removes higher frequencies while allowing lower frequencies to pass). Because it is in the path of the feedback, this has the effect of gradually attenuating the higher harmonics while keeping the lower ones, which corresponds closely with how a struck wire actually sounds.

Part 1: Modeling a piano wire (75%)

For the first part of this assignment, you are to implement a class that models a single piano wire. Your PianoWire class should provide the following constructor and methods:

public PianoWire(int wireNum)
The class constructor takes a single input, a non-negative integer that specifies the wire number (relative to middle C). That is, a parameter of 0 will produce a middle C string, 1 will produce C#, 2 will produce D..., etc. The constructor should initialize a queue containing N zeros, where N is the nearest integer to:

        SAMPLE_RATE * 2(22 - wireNum)/12 / 440

Here, SAMPLE_RATE is a constant defined in the StdAudio class, which was developed at Princeton.

public void strike()
This method simulates striking the wire by replacing all of the values in the queue with random values from the range -0.5 to 0.5. The size of the queue should remain unchanged.

public double sample()
This method returns the value currently stored at the front of the queue. It also updates the contents of the queue so that a different sample is obtained each time the method is called. The update adds a new value to the rear, which is the average of the two front values multiplied by a decay factor of 0.996, and removes the value from the front. See the diagram above for an example of this update operation.

You should test your class thoroughly by creating an object with a short queue and displaying the results of each update. Once you are convinced that the class is behaving as desired, you may integrate it with the provided Piano class. This class implements a simple piano, with keyboard keys mapping to individual wires. The routines for rendering the vibrations using your computer's sound card are contained in the utility class StdAudio. The routines for processing keyboard events are contained in the utility class StdDraw, which was also developed at Princeton.

Part 2: Extending the keyboard (25%)

Currently, the piano can only play one octave, going from middle C to high C. You are to modify your Piano and PianoWire classes so that three octaves are playable. If the user holds the Control key while hitting a key, the corresponding note in the lower octave should be played. For example, Control-s should play low C (one octave below middle C). Likewise, holding the Shift key should play a note in the upper octave. Note that Control-l and 's' should play the same note (middle C), as should 'l' and 'S' (high C).

As part of your modifications, you should add text to the display window that informs the user of the functionality of the Shift and Control keys.