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.)

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

• The files we have provided for you:
• Java     DoubleStack.java, Reverse.java
• Electronic Turnin: The files you should turn in: (Use the turnin utility to submit your project. This project is called "hw1" in the turnin system.)
• DoubleStack.java - source code in Java implementing the double stack
• Reverse.java - source code in Java for the reverse program described in section V. You only need to change this file if you go "above and beyond" the basic requirements, but turn it in in any case.
• README.txt - include the answers to the questions below.
• Written Turnin: Print the above three files and turn them in at the start of the class (printing instructions). Please make sure that you:
  • Prominently print your name, student #, and section in the top right corner of the first page.
  • Staple all sheets together, preferably using the same order listed above..
• README questions (include the number of each question)
1. (Answer this question before you begin) How long do you think this project would take you to finish? How much time did you actually spend on this project?
2. Who/What did you find helpful for this project?
3. How did you test that the final program is correct?
4. What happens if you exceed the maximum size of the DoubleStack? Can you think of other ways to handle this case? If you were to implement one of your ideas, which would it be, and why?
5. Let's pretend that, instead of a almost-functional DoubleStack class, you were given a fully-functional DoubleQueue class. How might you implement this project (ie, simulate a Stack) with one or more instances of a Queue? What is the runtime of a single top or pop operation?
6. In the previous question, what tradeoffs did you notice between a DoubleQueue implementation of a DoubleStack and your original array-based implementation? Which implementation would you choose, and why?
7. A description of how your project goes "above and beyond" the basic requirements (if it does)
8. What did you enjoy about this assignment? What did you hate? What could you have done better?
9. Any other information you would like to include.
• You may discuss the assignment with others in the class, but your solution must be entirely your own work!

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.

• Change the DoubleStack to grow when it becomes full.
• Try implementing the DoubleStack with a linked list instead of an array.
• Try implementing the Karplus-Strong algorithm (to generate "reverb" sounds). A description of this algorithm is available here.
• Assuming that your .dat input file contained a single note, try writing a program which will output a single-octave scale beginning at that note. Would the notes of an "evenly spaced" scale grow logarithmically, linearly, polynomially, or according to some other function?

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...