CSE 332 Winter 2012: Project 1 - Sound Blaster!

Outline

• Preliminaries
• Introduction
• The Assignment
  • Write-Up Questions
  • Above and Beyond
• Submission Information
• Sound & Sox
• Acknowledgments

Due Dates and Submission

You should submit using the Catalyst submission system linked on the course page:

https://catalyst.uw.edu/collectit/dropbox/jaf1978/19171

• Phase A: Wednesday Jan 11, before class
• Phase B: Wednesday Jan 18, before class

Be sure to read the submission instructions!

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.

Download these files into a new directory: Reverse.java, DStack.java, GStack.java.

The provided code will read a sound file, but does so in .dat format. You will use a program called sox to convert .wav files to .dat. Information about sox is here.

When you are ready to run your program and the sox program, 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. First, you'll implement stacks for Java double primitives. Then, you'll implement generic stacks and instantiate them with type Double.

Your Stack implementations will be used to do sound manipulation: 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). Click here for a history of this sometimes 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.

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 (i.e., not just those used by the reverse program).

The Assignment

You will write a program that reads a sound file in the .dat format (as 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 .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), to define the stacks you will implement. Your first job is to familiarize yourself with these files.

Phase A

To begin, 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 making changes to Reverse.java.

Phase B

For phase B, you need to provide two additional 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 copyArrayStack 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.

Note: Creating generic arrays can be a bit tricky at first; check out these notes for help (mainly workaround #1).

Running Your Program

The Reverse program takes four 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".
• In the "Arguments" tab, put the argument in the "Program arguments" box (e.g., list double in.dat out.dat).

To test your program, you will need a .dat file. You can create this from a .wav file as explained in the Digital Sound section. It may also be useful for you to manually create some short .dat files to aid in your testing.

Write-Up Questions

All questions are submitted with Phase B, but some of them (1-7) refer to work you did in Phase A. You may wish to start early.

Submit a report answering the following questions

1. Who and what did you find helpful for this project?
2. How did you test that your stack implementations were correct?
3. 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.
4. Other than java.util.EmptyStackException, did you use any classes from the Java framework or any other class library? As stated in the programming guidelines, you may get a low score on this project if you use a library to implement your stacks.
5. 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.
6. 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.
7. Why would a stack implementation using a queue, as you described in the previous question, be worse than your array and linked-list implementations of a stack?
8. In the process of making your generic stack implementations from your non-generic ones, what sort of errors did you encounter and how did you resolve them?
9. In hindsight, how much did you need to understand about the code in Reverse.java to make the changes to use your generic stacks?
10. Include a description of how your project goes "above and beyond" the basic requirements (if it does).
11. What did you enjoy about this assignment? What did you hate? What could you have done better?
12. 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 course grading policy. Note: please submit all extra credit files separately, as described under 'Submission'.

• (easy-ish) Modify your array implementations so that when the array is 3/4 empty, the stack resizes to use an array of half its current size.
• (harder) Implement the Karplus-Strong algorithm (to generate "reverb" sounds). A description of this algorithm is available here.
• (hardest) 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. It is fine if the note durations are decreasing.

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

• You should submit the following files, named as follows:

  Phase A:

  • ArrayStack.java
  • ListStack.java
    Although it is acceptable to submit a separate file for your node class, try using an inner class.

  Phase B:

  • 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 this zip decompresses its contents into a folder named extracredit and not into a bunch of individual files.

• As described in Grading Policies, Phase A and Phase B will be graded for both correctness and style. Our goal is to encourage appropriate attention to Phase A, while also incentivizing Phase B improvements whenever necessary.

  • Correctness points will be allocated to elements of Phase A and Phase B.

    • If you submit only one version of each file, then your correctness score is simply score(Phase A) + score(Phase B).
    • If you submit corrections or improvements to Phase A with Phase B, then your correctness score is score(original Phase A) + .5(score(improved Phase A) - score(original Phase A)) + score(Phase B). Be sure that your corrections or improvements do not introduce new bugs.

  • Style will be primarily graded using the final submitted version of your entire project. Phase A submissions must be reasonable, but we expect that you may reconsider elements of style in the course of Phase B.

• Do not submit DStack.java or GStack.java. You must not change these files. Your stack implementations must implement these interfaces as provided to you.

Sound and Sox

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.