CSE 373 Homework 1 - Sound Blaster!

Due: Thursday 10/08/2009.

Make sure you go through General Policies, Grading Policies, Written Homework Guidelines, 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!

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, 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. I would encourage you to try out Java Doc as well, but this is also not required (it is fine to use regular comments).

Outline

Introduction

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.

The Assignment

You will write a program that will take a sound file in the .dat format (explained below), and outputs 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. 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 top() 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. 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.

You should implement both versions of the stack interface without using any of the Java container library classes. In other words, no ArrayList or LinkedList. This means you will be implementing the interface using arrays (similar to how lists are implemented using arrays in section 3.2.1 on p. 58 of Weiss) and using a node class *you* create (similar to the linked list class in section 3.5 on p. 75 of Weiss which has a nested Node class, although you do not need to use Java Generics in your solution or provide the full set of List operations or Iterable methods shown in their solution).

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 (put these in a file called README.txt).

Writeup Questions

  1. The file secret.wav is a backwards recording of a word or short phrase. Use sox (or another converter) to convert the file to a .dat file, use the Reverse program to reverse it, use sox to convert the reversed file back to a .wav file, PLAY the .wav file by clicking on it, and write the phrase you hear as the answer to this question. (The exact sequence of commands is found here.)
  2. Did you use any classes from the Java framework or other class library? (If the answer to this question is anything other than "no", you're going to get a low score on this project!) Note: It is OK to use java.util.EmptyStackException.
  3. (2 parts) a) What happens if you exceed the maximum size of the array implementation of DStack? b) 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. Refering to comments you have inserted in your code is the best way to do this.
  4. 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. Assume your Queue class provides the operations enqueue, dequeue, isEmpty and size.
  5. 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?
  6. A description of how your project goes "above and beyond" the basic requirements (if it does).
  7. Any other information 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. A small amount of extra credit will be awarded to assignments that go beyond the basic requirements. 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.

Logistics for Project 1

It may be useful for you to create some short .dat files by hand to aid testing.

Submit your files via the catalyst drop box linked to our course web page. 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!

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

Sox

Yes, this is CSE373. 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 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.

There is a windows version of sox available at SourceForge. The source archive is known to compile and work on OS X 10.4. 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 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 [list/array] secret.dat secret-revealed.dat
  4. Convert it back to .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! 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.

Java Reminder

For this assignment you will need to instantiate an interface, DStack, in two different ways. The DStack interface defines a simple stack (shown here without comments): 

  interface DStack {
         boolean isEmpty();
         void push(double d);
         double 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. You don't need to duplicate the JavaDoc comments found in DStack.java on the individual methods in your ArrayStack and ListStack classes, but you should include other 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. I would recommend trying to use JavaDoc for your comments.

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

Getting started in 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.' Here are some starter instructions for doing the project in Eclipse on Windows.

First, be sure to check out this Eclipse tutorial from CSE 143.

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.

  1. Start Eclipse.
  2. 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.
  3. Follow the directions in the tutorial to create an empty project. Choose a name for the project (e.g. "cse373 hw01").
  4. Import the DStack.java and Reverse.java into your project. Go to File -> Import. Choose General -> File System. Click next and browse to find the folder where DStack.java and Reverse.java are on your file system. Select the check boxes next to their names and click finish.
  5. You should see DStack.java and Reverse.java in your project in the left-hand window (the package explorer). There will probably 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 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, epending 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 test your code, you'll need to do a bit of extra work in order to pass command-line arguments to the program:

  1. Right-click on Reverse.java. Go to Run As -> Run Configurations.
  2. When the dialog box pops up, click on "Java Application" and then select the 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, if you have your .dat files in the same directory as your workspace project folder:

list bot.dat out.dat

(That should all be on one line.) You will need to indicate the path to bot.dat if it is located in a different directory.

  1. Click Run. The program should run, with output appearing in the lower right window.
  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 the arguments.
  3. You'll need to run Sox on your output files separately to convert them from a .dat file into a .wav file.

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.