I. Introduction

The purpose of this assignment is to familiarize you with UNIX, to provide basic exposure to both C++ and Java, and to explore the use of the Stack ADT. Some introductory information about UNIX and C++ and Java can be found on this page. Once you are up and running with UNIX, you are ready to proceed to the Sound Blaster project. You will be required to turn-in working programs in both C++ and Java, but fear not, the amount of coding required should be light.

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 Satanic 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: ./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." In both C++ and Java, 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 (in both languages).

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. When you are looking through the files, try to think about any obvious differences you see between programming in Java and C++. What are the advantages and disadvantages of each? 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:
• C++     DoubleStack.hh, DoubleStack.cc, reverse.cc, Makefile
• Java     DoubleStack.java, Reverse.java
• The files you should turn in: (Use the turnin utility to submit your project. This project is called "project1" in the turnin system.)
• DoubleStack.cc - an implementation of DoubleStack.h in C++
• reverse.cc - source code in C++ for the reverse program described in section V
• DoubleStack.java - source code in Java implementing the double stack
• Reverse.java - source code in Java for the reverse program described in section V
• README.txt - an explanation of how to compile your programs (note: your programs should compile with g++ and javac on UNIX), a description of how your project goes "above and beyond" the basic requirements (if it does), and the answers to the questions below.
• README questions
• (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?
• Who/What did you find helpful for this project?
• 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?
• 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?
• 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?
• What are some of the advantages/disadvantages you found between Java and C++?
• What did you enjoy about this assignment? What did you hate? What could you have done better?
• What is your favourite music group/performer? Who would you most likely take to their concert: Brian, Hannah, or Albert?
• 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. 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) in the language of your choice (Java or C++). 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 the same assigment not so long ago...