COSC 072: Computer Science II

Project 2
Spring 2004

Due: Feb 20 @ 5 PM
6 points

In this project, you'll use a stack to determine if a string contains a balanced set of parentheses, and a queue to simulate customers being serviced at a deli counter.

  1. Copy the file p2.zip from my account on gusun to yours. At the gusun prompt type: 
    gusun% cp ~maloofm/p2.zip ./
    Unzip the archive by typing 'unzip p2.zip'. The archive will create a directory named p2/, so one should not exist prior to executing the unzip command.

    This archive contains a Makefile, the Simulation class, and the class definition for the Customer class. Make no changes to simulation.cc, simulation.h or customer.h. Read and follow the directions at the top of the Makefile.

  2. Using the Node<T> class, implement the Stack<T> class (i.e., using a linked list of Node<T> objects). Implement only the methods push, pop, and empty, the ones you'll need to complete this project. Also implement and use any necessary exception classes.

  3. Using the Node<T> class, implement the Queue<T> class (i.e., using a linked list of Node<T> objects). Implement only the methods enqueue, dequeue, and empty, the ones you'll need to complete this project. Also implement and use any necessary exception classes.

  4. Using the Stack<T> class, implement a class and method that determines whether a string contains a balanced set of parentheses, brackets, and braces. For example, if the String s = "{ ( a + b ) * c }", then s.balanced() would evaluate to true, whereas if s = "[ ( x * y } - z", then s.balanced() would evaluate to false.

  5. Implement the Customer class. The class definition is in the file customer.h, which came in the archive. Using this class, your Queue<T> class, and the Simulation class provided in the archive, run the customer-service simulation of a line at a deli counter.

    The Simulation::run method runs this customer-service simulation. At each time step, there is a 25% chance that a new customer will arrive. It numbers customers consecutively (i.e., the first customer gets number 1, the second, number 2, and so on). Customer requests vary in length from two to ten time steps. The default is that each run of the simulation consists of five customers. The Simulation::run calculates the average the average time customers spend waiting.

    The output of Simulation::run should look something like the following: 

    t1:
t2:
t3: Customer 1 arrives;
t4: Servicing Customer 1 with a job of length 5; Customer 2 arrives;
t5:
t6: Customer 3 arrives;
t7:
t8:
t9: Finished servicing Customer 1; Servicing Customer 2 with a job of length 4;
t10:
t11:
t12:
t13: Finished servicing Customer 2; Servicing Customer 3 with a job of length 8;
t14:
t15:
t16:
t17:
t18:
t19:
t20:
t21: Finished servicing Customer 3;
Average wait time: 10 minutes.

  6. Implement a main function that clearly demonstrates both solutions.

Use stepwise refinement and incremental development. For example, implement and test the Node<T> class before implementing the Stack<T> class.

You must provide a working UNIX Makefile with your submission. A Makefile is included in the archive. Follow the directions in the comments of the Makefile. We should also discuss the Makefile in class.

All class definitions and class methods must be documented with Doc comments. Doc comments for class definitions must include @author and @version tags. Doc comments for methods must include @param and @return tags, where appropriate.

Instructions for Electronic Submission: At the top of the file main.cc (or the file containing the main function), place the following header comment, with the appropriate modifications: 

//
// COSC 072 Project 2
// Name: <your name>
// ID: <GoCard ID>
// E-mail: <e-mail address>
// Instructor: Maloof
// TA: <TA's name>
//
// In accordance with the class policies and Georgetown's Honor Code,
// I certify that, with the exceptions of the class resources and those
// items noted below, I have neither given nor received any assistance
// on this project.
//

Although you may use any C++ compiler to develop your program, it must run under UNIX and must compile using GNU g++. You must also provide a working UNIX Makefile for your project.

If you need to include a message to your TA about your submission, then place the message in a file named README. Place the README file in the project directory p2/.

Before submitting, to reduce the size of the zip file, type 'make clean'.

To move up from the p2 directory, type 

gusun% cd ..
(Additional UNIX commands at the bottom of this page: HOWTO Compile under UNIX)

When you're ready to submit, change the name of the directory to your netid. For example, if your netid is maloofm, then rename the directory p2 by typing 

gusun% mv p2 maloofm
Create a zip file of the directory and its contents by typing 
gusun% zip -r p2.zip maloofm/*
This command creates a zip file named p2.zip by recursively (-r) copying all of the files (*) from the directory maloofm/.

To submit the zip file type 

gusun% submit -a p2 -f p2.zip
p2 is the name of the assignment (-a) and p2.zip is the file (-f) to be submitted for that assignment.

If the program submits the file successfully, you will receive a receipt by e-mail at the address <netid>@georgetown.edu.

Submit your project only once.

Once you've submitted your project, it is important to keep an electronic copy on a university machine (e.g., gusun or cssun) that preserves the modification date and time. If we lose your project or the submission system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.

You can also change the directory's name back to the original name. For example, 

gusun% mv maloofm p2
Note that changing the name of the directory does not change the dates of the files in the directory. You can also remove the zip file from your directory: 
gusun% rm p2.zip

The TAs who will be grading your projects this semester are listed on the main page. You must submit your project before 5 PM on the due date.

If you're running submit correctly and you see an error message labeled as SEVERE, then execute Plan B by using pine to submit your project as an attachment to an e-mail.

To accomplish this, at the gusun prompt, type 'pine'. When the menu appears, select the menu item for composing messages (C). In the To field, type the e-mail address cosc072maloof@cs. Attach your zip file. Control-T (symbolized ^T) will give you a list of files. Select the file to attach. The subject should be your netid followed by the extension .zip. For example, if your netid is maloofm, then the subject of the e-mail should be maloofm.zip. There's no need to include anything in the MESSAGE TEXT screen.

Once you've entered this information, the screen should look something like the following:

Finally, type ^X (Ctrl-X) to send the e-mail to the course account.