Project 1 - Sound Blaster!

Due Dates

Updates

(Dated updates will appear here for this assignment as they come up.)

Make sure you go through Grading Policy and Programming Guidelines before you begin working on the project. In particular, note that the README file you turn in is worth a substantial portion of the grade!

Outline

I. Introduction

The purpose of this project is 2-fold. First, we wnat to familiarize you with UNIX. Second, we want you to explore the uses of the Stack ADT.

To learn more about the Unix shell, we are going to write a simple shell script that will introduce you to some basics of Bourne shell scripting.

To explore the Stack ADT, we are going to use the DoubleStack data structure to do some cool sound manipulation. We are going to use a stack to reverse a sound wave (so we can hide secret messages in our rock songs). You say "Cool dude! But wait, CSE 143 never taught me how to work with music ..." Well, that's why we have the Sound Blast Background section.

If you have not progammed in Unix before and decide to try to do the Sound Blaster part of the project directly (not recommended) be sure to check out this very basic info on how to program in the Unix environment. Once you are up and running with UNIX, you should be able to proceed to the Sound Blaster portion.

II. Unix Warmups: Putting UNIX to Work for You

IIa. Backgound on Shells, Scripting, and how to setup your system

 Before we progress to sound manipulation and your future acceptance into Juilliard, let's try our hand a Bourne Shell scripting. In Unix, your command-line interface is usually called a shell. Shell scripting is very useful for doing textual manipulations, file manipulations, running repetitive sets of commands, setting up tests cases, and a number of other things.

There are many shells out there, just like that are many web browsers. The original, and one of the most common Unix shell types is the "Bourne Shell" named after its creator. The next most common shell type is called "C Shell" since its syntax tries (and fails) to take after the programming language C. It does not matter which shell you are logged in as. You can write scripts using either shell language and tell Unix to run your script under the correct shell. However, it may be less confusing if you change your shell to match the script language you will be learning. Do this by typing "chsh" and for the "New shell" type "/bin/bash". This will switch your shell to Bash (Bourne Again Shell -- the new generation of the Bourne Shell) which is the shell I recommend you to use.

IIb. Tutorial Links

Here are a couple of resources on how to do Bourne scripting:

IIc. Bourne Shell Scripting Assignment

 Now for your assignment. What you are to do is write two scripts with the following specifications:
  1. script1.sh - Files in a directory
  2. script2.sh - Counting

Turn in both these scripts along with your program below. Now onto the fun stuff, data structures and Java Programming...oh yeah, we're going to do some work with sound files too.

III. Sound Blaster: Your key to admissions into Juilliard

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

IIIb. Sox

Yes, this is CSE326. We're now going to show you how to use stacks to manipulate digital sound. The only thing that stands between you and your creative potential is a UNIX command-line utility called sox. sox stands for "SOund eXchange", and 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. The general strategy will be this:

  1. Take a .wav sound file of your choosing (e.g. my-mother-singing.wav) This sound shouldn't be longer than a couple seconds, or your program will run out of memory. If you can't find a sound, you can use the first few seconds of Break on Through by The Doors.
  2. Convert it to a .dat file: sox my-mother-singing.wav my-mother-singing.dat
  3. Manipulate it with the program you will write: java Reverse my-mother-singing.dat my-mother-singing-backwards.dat
  4. Convert it back to .wav file: sox my-mother-singing-backwards.dat my-mother-singing-backwards.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...

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

IIId. Assignment: Reversing a Sound File

Ok. Here's where you come in. You are going to take a .dat sound file, and output another .dat sound file, reversing the numbers in the second column (and only the numbers in the second column). This is going to create the trippy effect of "playing the sound backwards." We will provide you with a partial implementation of a DoubleStack class. Also, we will provide you with a program 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. Your first job is to look over the files which we provide you and become familiar with them.

Here's the catch! The stack implementation which we are giving you isn't complete. Currently, the reverse program doesn't work correctly because it pops elements from a faulty stack. In fact, it is very incomplete, but completing it shouldn't take you more than 20 lines of code (I did it in around 15 including spacing and comments). Once you fix the stack by correctly implementing its methods, the reverse program should work and create backwards sound files. For details on what to turn in for this assignment and how, read section IV on Logistics.

IIIe. README Questions

  1. (Answer this question before you begin) How long do you think this project would take you to finish?
  2. How much time did you actually spend on this project?
  3. Who/What did you find helpful for this project?
  4. How did you test that the final program is correct?
  5. What happens if you exceed the maximum size of the DoubleStack? Can you think of other ways to handle this case? If you were to implement one of your ideas, which would it be, and why?
  6. Let's pretend that, instead of a almost-functional DoubleStack class, you were given a fully-functional DoubleQueue class. How might you implement this project (ie, simulate a Stack) with one or more instances of a Queue? What is the runtime of a single top or pop operation?
  7. In the previous question, what trade-offs did you notice between a DoubleQueue implementation of a DoubleStack and your original array-based implementation? Which implementation would you choose, and why?
  8. A description of how your project goes "above and beyond" the basic requirements (if it does).
  9. What did you enjoy about this assignment? What did you hate? What could you have done better?
  10. Any other information you would like to include.

IIIf. Going Above and Beyond

The following list of suggestions are meant for you to try if you finish the requirements early.

IV. Logistics for Project 1

V. Acknowledgments

We would like to thank Adrien Treuille who would like to thank his own Data Structures professor, Timothy Snyder, who gave him a similar assignment a while ago...