CSE332 Summer 2012: Project 1 - Sound Blaster!
Outline
Due Dates and Turn-In
Phase A is due Monday, June 25 by 10PM
Phase B is due Monday, July 2 by 10PM
Read the submission information before you submit. Submissions with missing items will lose points.
Use the course dropbox to submit your assignment electronically.
Preliminaries
- Complete this project by yourself (i.e., without a partner). You may discuss the assignment with others in the class, but your solution must be entirely your own work.
- Go through the course policies (especially the Collaboration Policy) and the Programming Guidelines before you begin working on the project. In particular, note that the write-up you turn in is worth a substantial portion of the grade.
- Download these files into a new directory:
- Provided source code: Reverse.java DStack.java GStack.java
- Later, when you are ready to run your program and the sox program (see below), you will want these sound files: bot.wav secret.wav
Introduction
The purpose of this project is to implement a Stack ADT in the two most common ways: an array and a linked list. In Phase A, you will implement stacks for Java double numbers. In Phase B, you will implement generic stacks and instantiate them with type Double.
Your Stack implementations will be used to do sound manipulation, namely reversing a sound clip. Called "backmasking," this process was used by musicians including the Beatles, Jimi Hendrix, and Ozzy Ozbourne, although it seems to have fallen out of favor in recent years. (If interested, read about the history of this sometimes/often controversial practice.) "But wait," you say, "CSE 143 never taught me how to work with music." Don't worry — all the music-handling parts have been done for you.
Overall, your program will read a sound file in the .dat format (explained below), and write another .dat sound file which is the reverse of the first. We provide you with a class Reverse whose main method reads in a .dat sound file, pushes all the sound values on a stack, then pops them all off and writes them into a new .dat sound file. We have also provided interfaces DStack (for Phase A) and GStack (for Phase B). Your first job is to familiarize yourself with these files.
Even though the music-reversing code will use your stack implementations in only limited ways, you should test that your stacks are correct in all cases, not just those used by the reverse program.
Phase A
You need to provide two stack implementations, one using an array and one
using a linked list. They should be called ArrayStack and
ListStack. They should implement the provided DStack interface.
After you provide these implementations, Reverse should work and create
backwards sound files. It should take no more than a page or two of code to provide
the implementations. Your array implementation should start with a small array (e.g.,
10 elements) and resize to use an array twice as large whenever the
array becomes full, copying over the elements in the smaller array. Both
ArrayStack and ListStack should throw an
EmptyStackException if pop() or peek() is called when the
stack is empty. To use EmptyStackException, add the following line to your
file:
import java.util.EmptyStackException;
Note that your solution to Phase A does not require changes to Reverse.java.
Phase B
You need to provide two more stack implementations, these implementing the interface GStack<T>. Create classes called GArrayStack and GListStack that are just like ArrayStack and ListStack except that they are generic in the type of elements kept in the stack. The simplest approach is to copy ArrayStack and ListStack and then make appropriate changes. Normally such copy-and-paste is poor form, but here the pedagogical purpose is to show you how little code you must change to make the code generic. We want to grade all four stack implementations.
To use your generic stacks, you will need to make some additions to
Reverse.java to replace the 3 occurrences of:
System.err.println("no support for generics yet");
System.exit(1);
with appropriate code. Again, the code you write will be only slightly different
from non-generic code that is already there. Do not make other changes to
Reverse.java.
Running Your Program
The Reverse program takes 4 arguments (also known as "command-line
arguments"). The first is the word array or list, specifying which
implementation to use. The second is the word double or generic;
the latter is for Phase B. The next two are the input and output .dat file
names (include the .dat extension). From the command-line, you can run the
program with something like:
java Reverse list double in.dat out.dat
To run your program in Eclipse, create a "Run Configuration" (under the Run menu) and under the "Arguments" tab put the arguments (e.g., list double in.dat out.dat) in the "Program arguments" box.
To test your program, you will need a .dat file, which you can create from a .wav file as explained in the Digital Sound section. It may also be useful to create some short .dat files manually to aid testing.
Write-Up Questions
All questions are submitted with Phase B, but most of them can be answered based on work you did in Phase A, so you may wish to work on them before Phase B.
- Who and what did you find helpful for this project?
- How did you test that your stack implementations were correct?
- The file secret.wav is a backwards recording of a word or short phrase. Use sox (or another converter) and your program to reverse it, and write that as the answer to this question.
- Other than java.util.EmptyStackException, did you use any classes from the Java framework or other class library? (As indicated in the programming guidelines, you will get a low score on this project if you use a library to implement your stacks.)
- Your array stacks start with a small array and double in size if they become full. For a .dat file with 1 million lines, how many times would this resizing occur? What about with 1 billion lines or 1 trillion lines (assuming the computer had enough memory)? Explain your answer.
- Instead of a DStack interface, pretend you were given a fully-functional FIFO Queue class. How might you implement this project (i.e., simulate a Stack) with one or more instances of a FIFO Queue? Write pseudocode for your push and pop operations. Refer to the written homework guidelines for instructions on writing pseudocode. Assume your Queue class provides the operations enqueue, dequeue, isEmpty, and size.
- Why would a stack implementation using a queue, as you described in the previous problem, be worse than your array and linked-list stack implementations?
- In the process or making your generic stack implementations from your non-generic ones, what sort of errors did you encounter and how did you resolve them?
- In hindsight, how much did you have to understand about the code in Reverse.java to make the changes to use your generic stacks?
- Include a description of how your project goes "above and beyond" the basic requirements (if it does).
- What did you enjoy about this assignment? What did you hate? What could you have done better?
- Anything else you would like to include?
Going Above and Beyond
The following list of suggestions are meant for you to try if you finish the requirements early. Recall that any extra-credit points you earn for these are kept separate and will be used to adjust your grade at the end of the quarter, as detailed in the section on course grading.
- (least difficult) Modify your array implementations so that when the array is 3/4 empty, the stack resizes to use an array 1/2 its current size.
- (somewhat more difficult) Implement the Karplus-Strong algorithm (to generate "reverb" sounds). A description of this algorithm is here.
- (most difficult) Assuming that your .dat input file contained a single note, write a program to 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? For more information about the evenly-spaced scale, refer to this article. To earn full credit, you must start from an actual recorded note (not a synthetic one) and generate the single-octave scale.
Submission Information
- Each file you submit should have your name at the beginning. Text files should have your name on the first line. Source-code files should include your name in the comments at the beginning of the file.
- You must implement the list and array stacks by hand. You may not use any classes from the Java libraries to do the work. You should not use any import statements, except for java.util.EmptyStackException.
- For Phase A, turn in the following files, named as follows:
- ArrayStack.java
- ListStack.java Although it is acceptable to submit a separate file for your node class, try using an inner class.
- For Phase B, turn in the following files, named as follows:
- README.txt Answers to the Write-Up Questions.
- Reverse.java
- GArrayStack.java
- GListStack.java
- Any corrections or improvements to files from Phase A. If you submit new versions of files from Phase A, then also submit changes.txt describing what changes you made. This should be a concise description (as we can compare the files if we need details).
- Any additonal files for the extra credit in a zip file named extracredit.zip. Please make sure that this zip file decompresses its contents into a folder called extracredit and not into a bunch of individual files. Note the least-difficult extra credit should not need additional files.
- Do not turn in DStack.java or GStack.java. You must not change these files. Your stack implementations must implement these interfaces as provided to you.
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. But you don't need to understand ADC for CSE332.
Sox
The only sound file format you need to know about is the .dat format described below. You do not even have to know very much about that either, as we are giving you the code that reads and writes that format. In order to play sounds you produce, you need a way to convert between the .dat format and a format that common media players (Windows Media Player, winamp, RealPlayer, etc.) understand, such as .wav. We will describe one way to do it; however, you are free to use another converter.
sox is a Linux command-line utility whose name stands for "SOund eXchange". It lets you 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 useful because they are human-readable, text-based, sound files. Note that you will need to perform this conversion to answer one of the write-up questions.
There is a Windows version of sox
available, and the source archive
is known to compile and work on OS X 10.4. The program is also installed on the
department lab machines. You can download versions from the project page at SourceForge. The
Windows version is also a command-line program and works in the same way as the Linux
version described below. See here for some hints on using
it.
The general strategy for using sox
is as follows.
- Take a .wav sound file of your choosing (e.g., secret.wav). This sound should not be longer than a few seconds, or your program will run out of memory.
- Convert it to a .dat file: sox secret.wav secret.dat
- Manipulate it with the program you will write: java Reverse list double secret.dat secret-revealed.dat
- Convert it back to a .wav file: sox secret-revealed.dat secret-revealed.wav
- Listen to it with your favorite sound player.
That's all there is to it!
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. This 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.00018140590 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.22700680 -0.0115661620 0.22702948 -0.0145568850 0.22705215 -0.0145416260 0.22707483 -0.0121917720 0.22709751 -0.0123901370 0.22712018 -0.0145416260 0.22714286 -0.0144958500 0.22716553 -0.0147705080 0.22718821 -0.0157012940 0.22721088 -0.0129547120 0.22723356 -0.0127105710 0.22725624 -0.0181579590 0.22727891 -0.0191497800 0.22730159 -0.0145721440 0.22732426 -0.0122375490 0.22734694 -0.0124359130 0.22736961 -0.0108184810
Note that you should not have to deal much with the .dat file yourself, as the provided Reverse.java does all the work for you. All you have to do is implement the stacks. We are explaining the format because it will be helpful for you if you want to write a short file by hand to run, to help test your program.
Acknowledgments
Like many assignments, this has been passed down to us through the vaporous mists of time. Among all our fore-bearers, we would especially like to thank Ashish Sabharwal, Adrien Treuille, and Adrien's Data Structures professor, Timothy Snyder.