Homework 1 - Sound Blaster!

Assigned:     Tuesday, Sept 25, 2012

Due:             11:00pm, Thursday, Oct 4, 2012

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! You should do this assignment by yourself (i.e., without a partner).

Also note that for this assignment it is COMPLETELY allowable to help another student with these tasks: setting up Java or Eclipse, learning how to use Eclipse – including configuring it to run a program with command line parameters, setting up or learning how to use sox. I would encourage you to try using Eclipse, but do not let figuring out Eclipse prevent you from completing the assignment. There are some Java Doc comments in DStack.java. You are welcome to try out Java Doc as well, but this is also not required (it is fine to use regular comments). Have fun!

Outline

Introduction

The purpose of this project is to gain experience implementing a Stack ADT using an array and a linked list.

Your Stack implementations 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 controversial!) practice. "But wait," you say, "CSE 143 never taught me how to work with music..." Don't worry! The music-handling parts have been done for you.

The Assignment

You will use 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.

Implementing the Stack ADT

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 your implementations. For your array-based implementation, you should start with a small array (say, 10 elements) and resize to use an array twice as large whenever the array becomes full, copying over the elements in the smaller array.  It is recommended that you try doing this by using the Arrays.copyOf method found in java.util.Arrays. Although it will also be perfectly fine if you write your own loop or to use System.arraycopy.

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 only Java classes that you may use to complete the implementations of your Stacks are java.util.EmptyStackException and java.util.Arrays.  The only method that you can use in java.util.Arrays is the copyOf method to grow your ArrayStack when it becomes full.   You may use the length field of an array.

Running Reverse

The Reverse program takes 3 arguments (aka "command line arguments"). The first is the word array or list, and specifies which stack 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 box 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. See Working with Eclipse below for information on setting command line parameters in Eclipse)

Testing your Stacks

We have provided you a client program, Reverse.java, that uses the stack implementations you will write. Getting Reverse.java to run and correctly reverse a sound file is fun, and indicates that your stack implementations will compile and run. It does NOT however imply that your stack implementations have been thoroughly tested. Note that Reverse.java just uses your stacks in one particular way: pushing a bunch of elements onto the stack and then popping them all off. There are other ways that someone may want to use your stack implementations and other cases that are not necessarily tested by just being able to successfully listen to secret.wav in reverse.

We will be testing your stack implementations more generally, and you should too! We highly suggest creating another small client program of your own to help test other aspects of your Stack implementations behavior. You also might consider creating some short (~10 lines) .dat files by hand to aid testing (see the ".dat File Format" section of the write-up below for more information).

Writeup Questions

In addition, answer the following questions and provide the answer in the file README.txt:

  1. How did you test your code?
  2. 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.
  3. Let's pretend that, instead of a DStack interface, 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).
  4. 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?
  5. Include a description of how your project goes "above and beyond" the basic requirements (if it does).
  6. What did you enjoy about this assignment? What did you hate? What could you have done better?
  7. Any other information you would like to include.

Going Above and Beyond

If you finish the requirements early, you might be interested to try implementing the Karplus-Strong algorithm (to generate "reverb" sounds) for a small amount of extra credit. A description of this algorithm is available here.

Recall that any "extra-credit points" you earn are kept separate from your assignment score and may be used to adjust your grade at the end of the quarter, as detailed in the course grading policy. As these are "above and beyond", we will provide only very very limited help for these options. They are meant to be interesting things for you to explore on your own - have fun!

Logistics for Homework 1

The files we have provided for you:

 

You should turn in the following files, named as follows.  Please refer to the style guidelines posted on the homework page.

Turn-in should be done via the catalyst dropbox on our course web 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.

You may discuss the assignment with others in the class, but your solution must be entirely your own work! (e.g. follow the Gilligan's Island principle as discussed in the first day lecture slides.)

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.

Description: Z:\373-web\homework\hw01\ADC.gif

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

Sox

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

  1. 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.
  2. Convert it to a .dat file: sox secret.wav secret.dat
  3. Manipulate it with the program you will write: java Reverse secret.dat secret-revealed.dat
  4. Convert it back to a .wav file: sox secret-revealed.dat secret-revealed.wav
  5. Listen to it! (Use 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 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.

Java Reminder

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.

Feeling rusty on Java? You may also find it useful to refer to these slides from cse143 on arrays, list nodes, and linked lists(also here). In general you may find it useful to review a bit of the material from cse143. The resources found here may be helpful.

Working with Eclipse

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.' (NOT the similar sounding 'Eclipse IDE for Jave EE Developers').

First, be sure to check out an Eclipse tutorial.  There are several available on the web. Here is one by a cse 143 TA that describes downloading and "installing" Eclipse.

I would also encourage you to write and run a simple "Hello World" program using Eclipse before starting on the project. This is just a program that does nothing more than print out the string "Hello World". Once you have mastered "Hello World", you might try something with multiple files, or re-doing one of your projects from cse143.

Here are some starter instructions for opening the project in Eclipse.

  1. We've packaged the project files as an Eclipse project: 373au12proj1.zip. Download that file to your desktop.
  2. Open Eclipse.
  3. 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.
  4. Go to File -> Import. Choose General -> Existing Projects Into Workspace. On the next screen, choose 'Select archive file,' and browse to find the zip file you just downloaded and click open. You should see the Sound Blaster! project appear with a check box next to it. Press Finish.
  5. 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.
  6. 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.
  7. 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.
  8. We want to create a new Java class in a file, so choose the appropriate option. A dialog window pops up with various options - click Finish.
  9. 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?
  10. 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!

Running Your Program from Eclipse

When you've reached a point at which you want to try using your stack code with the Reverse.java program, you'll need to do a bit of extra work in order to pass command-line arguments to the program:

  1. 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.
  2. Select Java Application to show Reverse. Click on the Arguments tab.
  3. In the Program arguments box, put three arguments, as specified above: the type of stack, the input file and the output file. For example:

array data_files/bot.dat data_files/out.dat

(That should all be on one line.) In this example, data_files is a directory in your project folder where your input and output files are located. You may create a subdirectory called data_files in your project folder and place your .dat files there or you may find it easiest to put your .dat input and output files directly in the same directory as your .class files so that all you need to give is the file names themselves.

  1. Click Run. The program should run, with output appearing in the lower right window. If something did not work out (e.g. could not find your input .dat file, you gave the wrong number of input parameters) then you will get back a message about this. As you are debugging remember that you can always take a look at the Java code for Reverse itself to figure out what the problem might be.(
  2. 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.
  3. You'll need to run Sox on your output files separately.

When you've finished the project and want to turn in ArrayStack.java, ListStack.java, and ListStackNode.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 your desktop.

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, and Adrien Treuille and his Data Structures professor, Timothy Snyder.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to rea]