Project 1 - Sound Blaster!
Assigned: Wednesday, Jan 6
Due: Wednesday, Jan 13
- Electronic copy due at 11 PM. To turn in please use this
online dropbox.
Read directions before turning in! Bad
submissions may lose points!
- You should do this assignment by yourself (i.e., without a partner).
Make sure you go through General Policies,
Grading Policies and
Programming Guidelines
before you begin working on the project. In particular, note that the
writeup you turn in is worth a substantial portion of the grade!
Outline
The purpose of this project is to implement a Stack ADT in the two most
common ways, an array and a linked list.
Your Stack implementation will be used to do sound manipulation, namely
reversing a sound clip. This process, called "backmasking," was
used by musicians including the Beatles, Jimi Hendrix and Ozzy Ozbourne,
although it seems to have fallen out of favor in recent years.
Click here for a
history of this (sometime constroversial!) practice. "But wait,"
you say, "CSE 143 never taught me how to work with music..."
Don't worry! Most of the hard work has already been done.
You will write a program that reads a sound file in the .dat format
(explained below), and writes 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, puts the sounds values on a stack, pops
them off in reverse order, and puts these reversed values in a new .dat
sound file. We've also provided you with a DStack interface, which
defines a stack that holds double values. Your first job is to look over
these files and become familiar with them.
You need to provide two stack implementations, one using an array and
the other using a linked list. They should be called ArrayStack
and ListStack, respectively. They should implement the interface
DStack, which we provide to you. Once you provide these
implementations, Reverse should work and create backwards sound
files. It shouldn't take more than a page or two of code to provide the
implementation. Your array implementation should hold around a million
elements. You may assume that the array won't fill completely (although
we'll discuss what happens in that case in the writeup questions). 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;
The Reverse program takes 3 arguments (aka "command line
arguments"). The first is the word
array or list, and specifies which implementation to use.
The next two are the input and output .dat file names (you need to include
the .dat extension). Running the program will depend on your system; from a
command line it will look something like the following.
java Reverse list in.dat out.dat
In an IDE there is usually a dialog for setting program parameters
which contains a field for the program arguments. (e.g. in jGRASP
select Build->Run Arguments and a bar will appear at the top of
the screen that allows you to type in the arguments.)
Read the section on Digital Sound to learn how
to create a .dat file. To get you started, we've created a .dat file
here.
For details on what to turn in for this assignment and how, read the
section on Logistics. For a quick reminder of
how interfaces work in Java, see Java Reminder.
In addition, answer the following questions and provide the answer in your
writeup.
- Who/What did you find helpful for this project?
- How did you test that the final program is 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.
-
Did you use any classes from the Java framework or other class library?
(Remember, as stated in the
programming guidelines, if the answer to this question is anything
other than "no", you may get a low score on this project if you
use the library to implement your stacks!)
(Addendum: it's OK to use java.util.EmptyStackException!)
-
What happens if you exceed the maximum size of the array implementation of
DStack? Can you think of other ways to handle this case, if you
were allowed to change DStack.java and Reverse.java? Be
specific: refer to particular lines of code that would change, list any
exceptions you would add and who would throw them, describe who catches any
such exceptions and how they are handled, etc. Referring to comments you
have inserted in your code is the best way to do this. Give one good point
of your current implementation and one good point of the alternative
implementation you describe.
-
Let's pretend that, instead of a DStack interface, you were given a
fully-functional FIFO Queue class. How might you implement this
project (ie, 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.
(Addendum: Assume your Queue class provides the operations enqueue,
dequeue, isEmpty and size).
-
In the previous question, what trade-offs did you notice between a
Queue implementation of a Stack and your original
array-based implementation? Which implementation would you choose, and why?
- 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?
- Any other information you would like to include.
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 from your assignment score and will be used to adjust your
grade at the end of the quarter, as detailed in the
course grading policy.
- (1 point) Change the array implementation to grow when it becomes full.
-
(2 points) Try implementing the Karplus-Strong algorithm (to generate
"reverb" sounds). A description of this algorithm is available
here.
-
(5 points) 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? 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.
- The files we have provided for you:
It may be useful for you to create some short .dat files by hand to aid testing.
-
Each file you turn in should have your name at the beginning.
All text files should have your name on the first line; your name should
appear in the comments at the beginning of each source code file
you turn in.
-
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.
-
Electronic Turnin: You should turn in the following files, named
as follows:
-
ArrayStack.java. (Your array should hold around a million
elements.)
- ListStack.java. (While it is acceptable to
submit a separate file for your node class, try using an
inner class.)
-
README.txt, your writeup, containing the answers to each
assignment question.
-
Any 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.
Electronic turnin should be done via the online dropbox linked at
the top of this page. Note that you should not turn in
either
Reverse.java or DStack.java. This means you shouldn't
change them, either--your code must work with the original,
unmodified versions.
Your extra credit may include a modifed Reverse.java, but because
you've included it in a separate directory we'll be able to compile &
grade your regular assignment without touching your extra credit.
If you don't segregate your extra credit you may not receive credit for
it.
-
You may discuss the assignment with others in the class, but your
solution must be entirely your own work!
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.
The only sound file format you need to know about is the .dat format
described below. You don't even have to know very much about that either,
as we're giving you the code that reads and writes that format. In order
to play sounds you produce, you need a way to convert the .dat file into a
format that common media players (Windows Media Player, winamp, RealPlayer,
etc.) understand. We'll describe one way to do it below; however, you're
free to use any converter you can find.
sox is a UNIX command-line utility whose name stands for
"SOund eXchange". 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 useful because
they are human-readable, text-based, sound files. Note that you will need
to perform this conversion to answer one of the
writeup 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 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 UNIX version described below. Follow
this link 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 shouldn't be longer than a couple 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 secret.dat secret-revealed.dat
-
Convert it back to a .wav file:
sox secret-revealed.dat secret-revealed.wav
- Listen to it! (Use your favorite sound player.)
That's all there is to it!
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 for this assignment, you shouldn't have to deal much with the .dat
file yourself, as the provided Reverse.java does all the lifting
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 verify if your program works.
For this assignment you will need to instantiate an interface,
DStack, in two different ways. The DStack interface
defines a simple stack:
public interface DStack {
public boolean isEmpty();
public void push(double d);
public double pop();
public double peek();
}
An actual interface includes comments, including a description of how
pop() and peek() should behave if they are called
when the stack is empty.
To implement this interface, write a class as follows:
public class ArrayStack implements DStack {
public ArrayStack() {
// Your constructor code
}
public boolean isEmpty() {
// Your isEmpty() code
}
public void push(double d) {
// Your push() code
}
// continue with the rest of the functions,
// along with any member variables, etc.
}
The ListStack class should be defined similarly. You should
include appropriate comments as needed. In particular, each file
should begin with a comment that describes the class in the file,
and includes your name and other identifying information.
We encourage you to try working on your project in
Eclipse, a powerful environment for
Java and a number of other languages. Eclipse may seem like overkill for
this assignment - probably because it is! But as the projects get larger,
having an integrated development environment with lots of features will
come in handy, so you should consider trying it out now.
You can use Eclipse in the lab, or download it to your personal machine. The
download site offers a
number of different versions; you'll want 'Eclipse IDE for Java Developers.'
(I've not had much luck getting Eclipse to run remotely over an X connection,
and even if you could get it to work I'm guessing it would be pretty slow.)
Here are some starter instructions for opening the project in Eclipse. I was
working on a Linux machine in the basement lab; the Windows version may be
slightly different.
-
I've packaged the project files as an Eclipse project:
326wi10proj1.zip. Download that file to
your desktop.
-
Open Eclipse by going to Applications -> System Tools -> Terminal and
typing:
eclipse &
at the prompt.
-
If this is the first time you've run Eclipse, it will ask you to choose a
location for a workspace. The default location is probably fine.
-
Go to File -> Import. Choose General -> Existing Projects Into Workspace.
Choose 'Select archive file,' and find the zip file you just downloaded.
Press Finish.
-
There should now be a Sound Blaster! project in the left-hand window.
There should be little red Xs on some of the files and folders - this
means that the code has errors in it. As you edit the code, Eclipse
will automatically rebuild and tell you if you've made an error.
-
Find Reverse.java in the project and double-click. The file pops up.
Now you can scroll down and hover on little light bulb in the left margin
to see what the errors in the code are.
-
Looks like we don't have classes named ListStack or ArrayStack yet - which
makes sense, as those are the files you need to write for your assignment.
Here's where Eclipse gets really useful. Click on the lightbulb - Eclipse
pops up a list of possible remedies.
-
We want to create a new file, so choose the appropriate option. A dialog
window pops up with various options - click Finish.
-
Eclipse auto-generates the file ListStack.java (or ArrayStack.java,
depending which lightbulb you clicked) with stub methods for all of the
methods in the DStack interface. Nifty, huh?
-
At this point I'll let you figure out how to work in Eclipse on your own.
For this assignment, you won't really need any of Eclipse's cool features
- but feel free to explore!
-
When you've reached a point at which you want to test your code, you'll
need to do a bit of extra work in order to pass command-line arguments
to the program:
- Right-click on the Reverse.java file in the Sound Blaster!
project on the left hand side of the screen. Go to Run As ->
Run Configurations.
- Click on the Arguments tab.
-
In the Program arguments box, put three arguments, as specified above:
the type of stack, the input file and the output file. or example:
array /homes/iws/username/Desktop/bot.dat
/homes/iws/username/Desktop/out.dat
(That should all be on one line.) where
/homes/iws/username/Desktop is your Linux Desktop.
-
Click Run. The program should run, with output appearing in the
lower right window.
-
To run the program again with the same arguments, press the
Run button in the toolbar. If you want to run the program
again with different arguments, you'll need to go back to
the run dialog and change what you typed in earlier.
- You'll need to run Sox on your output files separately.
-
When you've finished the project and want to turn in ArrayStack.java and
ListStack.java, an easy way to get the individual files is to click on
each one in Eclipse's left-hand window and drag to the Desktop. This
copies the file from the Eclipse workspace to
/homes/iws/<username>/Desktop.
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, and Adrien Treuille and his Data Structures professor,
Timothy Snyder.
CSE Home 
