Homework 1
Sound Blaster!
Electronic Turnin Due Monday June 30, by 11PM
Paper Copy Due Wed July 2, at start of class

I. Introduction

The purpose of this assignment is to familiarize you with UNIX, and to explore the use of the Stack ADT. First, check out this very basic info on how to program in this environment. Once you are up and running with UNIX, you are ready to proceed to the Sound Blaster project.

In this project we are going to use the DoubleStack data structure to do some cool sound manipulation. We are going to use a stack to reverse a sound wave (so we can hide secret messages in our rock songs).  Cool dude! But wait, CSE 143 never taught me how to work with music ...

II. How Digital Sound Works

We will view sound as a continuous function of time from the positive real numbers (time) to the interval [-1.0, 1.0] (amplitude). Since a computer can't "hold" a function defined on the reals, we have to approximate the function. We do this by measuring (or "sampling") the sound several thousand times per second.

This process is called "Analog to Digital Conversion", or ADC. The number of times per second the sound is sampled is called the sample rate and is measured in Hertz. For example, CDs are recorded at 44100 samples per second, or 44.1kHz. Wait a minute! Is this the right class? I thought this was CSE326.

III. Sox

Yes, this is CSE326. We're now going to show you how to use stacks to manipulate digital sound. The only thing that stands between you and your creative potential is a UNIX command-line utility called sox. sox stands for "SOund eXchange", and it allows you to convert between many different sound formats including .wav, .au, etc... In particular, sox allows you to convert to and from .dat sound files. .dat files are cool because they are human-readable, text-based, sound files. The general strategy will be this:

  1. Take a .wav sound file of your choosing (e.g. my-mother-singing.wav) This sound shouldn't be longer than a couple seconds, or your program will run out of memory. If you can't find a sound, you can use the first few seconds of Break on Through by The Doors.
  2. Convert it to a .dat file: sox my-mother-singing.wav my-mother-singing.dat
  3. Manipulate it with the program you will write: java -classpath . Reverse my-mother-singing.dat my-mother-singing-backwards.dat
  4. Convert it back to .wav file: sox my-mother-singing-backwards.dat my-mother-singing-backwards.wav
  5. Listen to it! (You can use any sound player.)
That's all there is to it! But before we get too excited, let's first explain...

IV. The .dat File Format

The .dat file format starts with one line describing the sample rate of the sound file. This line is required. The rest of the file is composed of two columns of numbers. The first column consists of the time (measured in seconds) when the sample was recorded, and the second column contains the value of the sample, between -1.0 and 1.0. Here is the beginning of a sample .dat file. Notice that the numbers in the first column increase by 1/44100 each step. This is because the sample rate is 44.1kHz.

; Sample Rate 44100
0             0
2.2675737e-05 0
4.5351474e-05 0
6.8027211e-05 0
9.0702948e-05 0
0.00011337868 0
0.00013605442 0
0.00015873016 0
0.0001814059  0
0.00020408163 0

Here is the same file, a little deeper on:

0.22693878    -0.0062561035
0.22696145    -0.0043945312
0.22698413    -0.0068664551
0.2270068     -0.011566162
0.22702948    -0.014556885
0.22705215    -0.014541626
0.22707483    -0.012191772
0.22709751    -0.012390137
0.22712018    -0.014541626
0.22714286    -0.01449585
0.22716553    -0.014770508
0.22718821    -0.015701294
0.22721088    -0.012954712
0.22723356    -0.012710571
0.22725624    -0.018157959
0.22727891    -0.01914978
0.22730159    -0.014572144
0.22732426    -0.012237549
0.22734694    -0.012435913
0.22736961    -0.010818481

V. Reversing a Sound File

Ok. Here's where you come in. You are going to take a .dat sound file, and output another .dat sound file, reversing the numbers in the second column (and only the numbers in the second column). This is going to create the trippy effect of "playing the sound backwards." We will provide you with an implementation of a DoubleStack class. Also, we will provide you with a program reverse which reads in a .dat sound file, puts the sounds values on a stack, pops them off in reverse order, and puts these reversed values in a new .dat sound file. Your first job is to look over the files which we provide you and become familiar with them.

Here's the catch! The stack implementation which we are giving you isn't complete. You need to implement correctly the top and pop methods. This shouldn't take more than a couple lines of code. Currently, the reverse program doesn't work correctly because it pops elements from a faulty stack. Once you fix the stack by correctly implementing these two methods, the reverse program should work and create backwards sound files. For details on what to turn in for this assignment and how, read section VI.

VI. Logistics for Project 1

VII. Putting UNIX to Work for You (Optional)

Did you find yourself repeatedly entering the same commands? (e.g. to run Reverse and then convert the resultant file). This is a simple example of where UNIX shell scripts can save you lots of time, and you may find them particularly useful for testing your programs later in this course.

If you have time, look at the csh scripting tutorial. Then try writing the shell scripts requested by question 2 of this old homework. When you're finished or need help, check out the solutions -- but you'll learn a lot more if you get it working first! You can also ask for help from the course staff or from your neighbors in the lab.

VII. Going Above and Beyond

The following list of suggestions are meant for you to try if you finish the requirements early.

VIII. Acknowledgements

We would like to thank Adrien Treuille who would like to thank his own Data Structures professor, Timothy Snyder, who gave him a similar assigment not so long ago...