Last Updated: March 29, 2014 by HyeIn Kim
CSE 332 Spring 2014

CSE 332 Project 1: Sound Blaster!

Outline

• Due Dates & Important notes
• Turn in Information
• Introduction
• The Assignment
• Phase A Programming
• Phase B Programming
• Above and Beyond (Part of Phase B)
• Acknowledgments

Due Dates & Important notes

Due Dates

• Phase A: Monday April 7, 11:59pm
• Phase B: Thursday April 10, 11:59pm

Important notes

• 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.
• Read Collaboration Policy, Grading Policy, and Programming Guidelines before you begin. In particular, note that the write-up is worth a substantial portion of the grade.
• Each file you turn in should have your name at the top of the file.
• You must implement the list and array stacks by hand. You should not use any classes from Java libraries (You should not use any import statements, except java.util.EmptyStackException).
• You must not change the provided DStack.java and GStack.java files, and your stacks must implement these interfaces as provided to you.
• Any extra credit must be attempted after finishing & turning in all codes for phase B. *DO NOT MIX* your extra credit stuff with your phase B files!
• Your code should not contain any compile warnings. In GArrayStack, you will encounter a non-avoidable warning which you are allowed to suppress using @SuppressWarnings("unchecked") annotation. However, you are NOT allowed to suppress any other warnings, you should instead fix your code to remove the warnings.
• How digital sound works, and a link for a wav to dat conversion program: here.
• A few tips on using sox here.

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

• GArrayStack.java
• GListStack.java
• ArrayStack.java (If you made any improvements from Phase A)
• ListStack.java (If you made any improvements from Phase A)
• Reverse.java
• README.pdf (Answers to the Write Up Questions)
• Testing code (either java file or script file)
• extracredit.zip (Optional, only if you did Above & Beyond)

Do not turn in DStack.java and GStack.java, and llease make sure that extracredit.zip decompresses its contents into a folder called extracredit and not into a bunch of individual files.

Introduction

The purpose of this project is to implement a Stack ADT in the two most common ways, an array and a linked list. In phase A, you'll implement stacks for Java double numbers. Then in phase B, you'll implement generic stacks and instantiate them with type Double.

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

The Assignment

• The code provided for you will read in a sound file, but it does so in .dat format. You'll use a program called sox to convert wav files to .dat: You can find information on it here and also on how to use it here.
• Later, when you are ready to run your program and the sox program, you will want these sound files: bot.wav, secret.wav

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, pushes all the sound values on a stack, then pops them all off and writes them into a new .dat sound file. We've also provided you interfaces DStack (for Phase A) and GStack (for Phase B), which define the stacks you will implement. Your first job is to familiarize yourself with these files. The music-reversing code will use your stack implementations in only certain ways, for this project, you should test that your stacks are correct in cases other than those used by the Reverse program.

Phase A Programming

For phase A, you need to provide two stack implementations, one using an array and one using a linked list. They should be called ArrayStack and ListStack, respectively. They should implement the DStack interface given to you. Once 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 an array of size 10 elements and resize to use an array twice as large whenever the array becomes full, copying over the elements in the smaller array.
• When growing your array, do your copying "by hand" with a loop, do not use Arrays.copyOf or other similar methods. It is good to know that these methods exist, but for now we want to focus on understanding everything that is going on "under the covers" as we talk about efficiency. Using the length property of an array is perfectly fine.
• For your linked list implementation, you should implement your own linked list nodes and build a stack out of those, similar to the slides from lecture 1 that do the same thing for a queue. You should *NOT* be using any classes from Java collections. You may include your node class as a separate file (Don't forget to submit this file!) or as a nested/inner class. Either will be fine.
• 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 Programming

For phase B, you need to provide two more 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 copy ArrayStack 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 you need to change to make the code generic — and we want to grade all four stack implementations. To use your generic stacks you will need to modify Reverse.java by replacing 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 (mainly workaround #1) for help.

Running Your Program

The Reverse program takes 4 arguments (a.k.a. "command-line arguments"). The first is the word array or list, and specifies 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 (you need to 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" and under the "Arguments" tab put the arguments (e.g., list double in.dat out.dat) in the "Program arguments" box. Here are some more tips about using Eclipse with Project 1. To run Reverse, you will need a .dat file, which you can create from a .wav file as explained in the Digital Sound section. It may also be useful for you to create some short .dat files by hand to confirm that you are getting the right results.

Write up (Due with Phase B)

Submit a README.pdf file, answering the questions in this template README file: (README.docx, README.pdf)
Note that the write-up questions can all be turned in for Phase B, but some of them (1-7) refer to work you did in Phase A, so you may wish to start on them early.

Above and Beyond (Due with Phase B)

The following list of suggestions are meant for you to try only if you finish the requirements early. Please be sure that your stack implementations have been thoroughly tested and you have checked your writeup carefully before attempting any of these (Completed phaseB and turned in all phaseB code). Recall that any extra-credit you complete is noted and kept separate in the gradebook and *may* be used to adjust your grade at the end of the quarter, as detailed in the course grading policy.
Note: please turn in all extra credit files separately, as described under 'Turn-in'. DO NOT MIX it with Phase B code!
Note: You need to describe each of your implementations in detail in your write-up to get credit

1. (least difficult) Modify your array implementations so that when the array is 3/4 empty, the stack resizes to use an array of half the size.
2. (somewhat more difficult) Implement the Karplus-Strong algorithm (to generate "reverb" sounds). A description of this algorithm is available here.
3. (most difficult) 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's fine if the note durations are decreasing.

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.