Project
1 - Sound Blaster!
Due: Wednesday October 10
- Electronic copy due at
11:59pm. To turn in please use the Assignment Dropbox link to the left.
Read directions before turning in! Bad
submissions may lose points!
- Hand in hardcopy (code
& written questions) in class (details to come)
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, a static array and a linked list.
Your Stack implementation will be used to do
sound manipulation, namely reversing a sound clip. This tool was used by
musicians including the Beatles, Jimi Hendrix and Ozzy Ozbourne, although it
seems to have fallen out of favor in recent years. "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
will take a sound file in the .dat format (explained below), and output
another .dat sound file which is the reverse of the first. We provide you
with a class 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. 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.
Now for the work! 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 this
implementation, 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. The Reverse program takes 3 arguments. The first is either array or list, and specifies which implementation to use. The next two
are the input and output .dat files (you need to provide the .dat extension).
Running the program will depend on your system; from the 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.
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.
Writeup
Questions
- 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're going to get a low score on this project!)
- a. 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.
b. What happens if you call top or pop on an empty stack in 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.
- 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?
- 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.
- Change the array
implementation to grow when it becomes full.
- 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? For more information about the evenly-spaced scale, refer to this article.
- 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 a comment at the
beginning of all source code you turn in.
- You cannot use
any classes from the Java framework. The rule of thumb is that you
should not use the import
statement at all. The Reverse
class needs to import some things, but your classes do not. You will
lose half of your score if you do!
- Electronic Turnin:
You should turn in the following files, named as follows:
- ArrayStack.java. Your array should
hold around a million elements.
- ListStack.java
- 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.
Electronic turnin should be done via the Assignment Dropbox link to the left.
Note that you do 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 probably
won't receive credit for it!
- Hardcopy Turnin: In
class, turn in hardcopies of each file turned in electronically.
Remember your name! Please add your section as well (AA, AB).
- ArrayStack.java
- ListStack.java
- README.txt, containing the
answers to the assignment questions.
This should be a text file (like from notepad), not a Word
document or anything else.
To combine your files and
print your homework double sided (to save paper) use the commands:
a2ps -A
fill -o username-prj1.ps *Stack.java README.txt
lpr -Pprintername -h -oDuplex=DuplexNoTumble
Please make sure you have
printed these files in a legible manner. If it's difficult for your TAs to
read or grade them, you will lose points.
- 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.
Sox
Yes, this is 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.
There is a windows version of sox available at SourceForge.
It seems to work well, but download and run at your own risk. It is also a
command-line program and works in the same way as the UNIX version described
below.
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 cool 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.
The general strategy 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
.wav file: sox
secret-revealed.dat secret-revealed.wav
- Listen to it! (Use
your favorite sound player.)
sox has been installed in the cse326 course directory. In
order to use it conveniently on the command line, you should put it in your
path by doing something like the following: export
PATH="/cse/courses/cse326:$PATH". See the Unix tutorials on the very useful ACM Tutorials
page for more help on Unix.
If you get a command not found error when trying to do the export mentioned above, it's probably because you're in the tcsh shell. Given your TAs unfamiliarity with that shell, the
easiest thing to do is type bash to enter the bash shell, at which point the export command should work as advertised.
That's all there is to it! But before we get
too excited, let's first explain...
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
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 telling you the format because it will be
helpful for you 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:
interface DStack { boolean isEmpty(); void push(double d); void pop(); double top(); }
To implement this interface,
write a class as follows.
class ArrayStack implements DStack { public ArrayStack() { // Your constructor } public boolean isEmpty() { // Your isEmpty() } public void push(double d) { // Your push() } // continue with the rest of the functions, // along with any member variables, etc. };
The
ListStack class should be defined similarly.
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 
