Skip to main content
CSE 331: Software Design & Implementation

CSE 331 Homework 5: Office Hours Queue

Due Wednesday, May 20 at 11:59pm.

In this homework you will build a simple terminal application to manage students in an office hours queue who are waiting to be helped.

Starter code

Go to the CSE 331 public gitlab repository in the hw05 folder. Click the blue "Code" button in the top right, and the click Download directory as zip at the very bottom of the popup. Extract the resulting file on your machine. You should see the following files:

  • OfficeHoursQueue.java: the specification for the queue data structure
  • OfficeHoursQueueImpl.java: starter file for your implementation of the queue data structure
  • OfficeHoursQueueSpecTest.java: starter file for your specification-based tests
  • OfficeHoursQueueImplTest.java: optional starter file for your implementation-based tests
  • OfficeHoursTerminalApp.java: starter file for your terminal application
  • lib/: JUnit jar.
  • Makefile: shortcuts for compiling and running (see below).

Software setup

You may use any Java development environment you want. If you have one you are already comfortable with, we recommend you use it.

Visual Studio Code

If you are looking for a Java development environment, we recommend Visual Studio Code because it is easy to set up. You will need the "Extension Pack for Java". (Open the extensions panel in VS Code and search for "Extension Pack for Java" and install it.)

Once you have VS Code and the extension pack installed, then:

  1. Use File -> Open Folder... and select the unzipped hw05 folder you downloaded earlier.
  2. Open the OfficeHoursTerminalApp.java file.
  3. You should see a "Java activating" message near the bottom of your window.
  4. Once it is finished activating, you should see a green "Run" button above the main method in OfficeHoursTerminalApp. Press the run button to run the starter code and confirm that your setup is working.

The rest of the starter code (in particular OfficeHoursQueueImpl.java) will not compile due to unimplemented methods until you have finished Task 1 below.

Using the command line

Alternatively, you can run the code from the command line. From the unzipped hw05 directory,

make compile     # compile everything
make run         # run the terminal app
make test        # run all tests
make clean       # delete compiled .class files

The Makefile should work on macOS, Linux, and Windows (you'll need to install Make if you don't already have it). You can also copy paste the commands out of the Makefile to run them directly if you don't have Make.

These make targets will exit with error in the starter code due to unimplemented methods until you finish task 1 below.

Task 1: Implement and test the queue

Read the specification of OfficeHoursQueue carefully. It describes an ADT representing the office hours queue.

Once you have read the required interface, then you should:

  1. Write your implementation in OfficeHoursQueueImpl.java.
  2. Write tests, split across two files as described below.

Specification-based vs implementation-based testing

A specification-based test relies only on behavior described in the specification. It would pass when run on any correct implementation of the spec, including yours, your classmate's, or the course staff's.

An implementation-based test additionally relies on choices a particular implementation made. These are most often choices about behavior that the spec leaves unspecified. For example, what happens when a method is invoked on an input that violates a @requires? That behavior can only be tested in an implementation-based way. These tests may be useful for your own development, but they might not pass when run on a different but equally correct implementation.

For this reason, we have given you two different test files:

  • OfficeHoursQueueSpecTest.java contains only specification tests, that is, tests that only depend on behavior guaranteed by the OfficeHoursQueue specifciation.
  • OfficeHoursQueueImplTest.java contains any additional tests you want to write that may depend on behavior unique to your implementation

We've given you one example test in OfficeHoursQueueSpecTest.java. You'll need to add many more to satisfy the coverage and bug-detection requirements below.

Only your specification tests in OfficeHoursQueueSpecTest.java will be graded. Specifically, we will grade your tests by:

  1. Run your spec tests against your implementation. They must all pass.
  2. Run your spec tests against the staff implementation, and possibly other correct implementations. They must all pass against those too. (If they don't pass when run against a different but still correct implementation, then that is an indication that the tests are testing behavior not required by the spec.)
  3. Measure the coverage of your implementation under your spec tests. You must achieve the 331 testing guidelines (statement, branch, and loop coverage) using only spec-based tests. (Recall that code that cannot be reached by allowed inputs is not required to be covered by the 331 guidelines.)
  4. Run your spec tests against several deliberately buggy implementations we've prepared. Some points will be awarded based on how many of these buggy implementations your tests detect (i.e., cause to fail). A good test suite is able to distinguish correct implementations from incorrect ones. Tests that exercise a method but don't actually check meaningful behavior (e.g., calling a method without asserting anything about the returned value) won't catch many bugs.

So on the one hand, your spec tests must be thorough enough to catch buggy implementations. But on the other hand, your spec tests must not test any behavior that is not required by the specification.

The implementation test file will not be graded. You may leave it blank if you wish.

Task 2: The terminal application

Build a small interactive terminal application in OfficeHoursTerminalApp.java that lets a TA manage the queue from the command line. Use the OfficeHoursQueueImpl data structure implementation you wrote in Task 1.

The starter code for the terminal app includes a small "counter" demo to show you the basics of how to use a Scanner to make an interactive terminal application. You should delete this starter code and replace it with your real application.

You have the freedom to design the specifics of how the terminal application works, as long as your application supports all of the functionality described below. As long as a user can do each of the things in the scenarios below, you're free to design the interface however you like.

You do not need to submit JUnit tests for the terminal application. But you should run the application yourself and ensure that all required behavior works as desired. Course staff will grade your terminal application by running it and trying it themselves.

Required functionality

The application must let the user:

  • Add a student to the back of the queue, with a name and an optional question.
  • Remove a named student from the queue (e.g., the student gave up waiting).
  • Help the next student, dequeueing them from the front of the queue and displaying their name and question.
  • Cut in line: This inserts a new student into the queue immediately after a given existing student. (Useful when a TA wants to handle a small follow-up question right after the student in front of it.)
  • Quit the application cleanly.

As a user-facing application, it should be mostly self-documenting: a user who has never run it before should be able to figure out what to do. At a minimum, the program should print a menu of available commands (or otherwise display the available options) so the user doesn't have to guess. It should also handle all inputs reasonably and with decent error messages. For example, if the user tries to help a student when the queue is empty, then the program should not crash, but rather should print an error message and continue.

Example Scenario

The following scenario illustrates the required functionality. Your application should be able to handle equivalent functionality, though you are free to use a different menu format and display information differently. Of course, just being able to handle this one example scenario correctly does not mean your code is correct in all cases.

It's a Monday morning. TA Pratika opens office hours and starts the application. Three students arrive in quick succession:

  • Alice, with the question "what is an ADT?"
  • Bob, with no specific question
  • Carol, with the question "segfault in HW4"

The queue now has three students waiting.

commands: join, leave, dequeue, cut, quit
> join
name: Alice
question (blank for none): what is an ADT?
added Alice

commands: join, leave, dequeue, cut, quit
> join
name: Bob
question (blank for none): 
added Bob

commands: join, leave, dequeue, cut, quit
> join
name: Carol
question (blank for none): segfault in HW4
added Carol

commands: join, leave, dequeue, cut, quit
>
Three students join the queue: Alice, Bob (no question), and Carol.

Pratika starts with the front of the queue and helps Alice. The application dequeues Alice and displays her name and question. The queue is now Bob, Carol.

...
> dequeue
now helping Alice: what is an ADT?

commands: join, leave, dequeue, cut, quit
>
Pratika dequeues Alice. The queue is now Bob, Carol.

A few minutes later, Alice comes back with a quick follow-up question. Pratika doesn't want to send her to the back of the queue, so she inserts Alice immediately after Bob. Alice has cut in line! The queue is now Bob, Alice, Carol.

...
> cut
after whom: Bob
name: Alice
question (blank for none): follow-up: still confused
inserted Alice after Bob

commands: join, leave, dequeue, cut, quit
>
Alice cuts in after Bob. The queue is now Bob, Alice, Carol.

Just then, Bob remembers he has to run to another class and won't be able to wait. Pratika first types "Bub" by mistake when trying to remove him. The application reports that no such student is in the queue and continues running normally. She tries again with "Bob" and the removal succeeds. The queue is now Alice, Carol.

...
> leave
name: Bub
Bub is not in the queue

commands: join, leave, dequeue, cut, quit
> leave
name: Bob
removed Bob

commands: join, leave, dequeue, cut, quit
>
The typo `Bub` is rejected; `Bob` is then removed successfully.

Pratika helps Alice's follow-up, then helps Carol. The queue is now empty. Pratika tries to help one more student, just to see what happens. The application reports that there's no one waiting and continues running normally without crashing.

...
> dequeue
now helping Alice: follow-up: still confused

commands: join, leave, dequeue, cut, quit
> dequeue
now helping Carol: segfault in HW4

commands: join, leave, dequeue, cut, quit
> dequeue
queue is empty

commands: join, leave, dequeue, cut, quit
>
The remaining students are helped, then an extra `dequeue` on the empty queue reports an error without crashing.

Office hours are over. Pratika quits the application; it exits cleanly.

...
> quit
goodbye
The `quit` command prints `goodbye` and exits the program.

Correctness and code quality

In addition to evaluating your tests (Task 1), we will grade your queue ADT implementation and your terminal application on correctness and on code quality.

A passing test suite is good, but it does not guarantee that your code is correct. Despite this, you are responsible for turning in code that works, and for doing the work to convince yourself that it works. You should reason carefully about the spec, trace through your code and ensure it satisfies the spec in all cases.

Be sure your queue ADT implementation follows all the rules for implementing an ADT in 331. You must document in a comment the AF and RI, define and call checkRep(), and defensively check fast preconditions.

The starter code already includes specifications for every method on the queue interface, so you don't need to write any new specs in OfficeHoursQueueImpl.java. But your implementation must satisfy the specs we've given you.

Using AI

You are welcome to use AI assistance on this assignment, but you are not required to. AI may speed up some parts of this assignment, at the cost of reducing your own understanding of the code you are submitting. We leave it to you to navigate this tradeoff responsibly. Importantly, we believe that we have taught you everything you need to know to do well on this assignment by yourself.

Using AI does not absolve you of the responsibility to turn in high-quality, correct code. We will grade your submission the same way regardless of how it was produced; you are accountable for everything submitted under your name.

You also must describe your use of AI, if any, in the reflection questions below.

You do not need to submit full transcripts of your AI usage for this assignment.

Reflection

Submit a short text file called REFLECTION.txt answering the questions below.

  1. Which lines of OfficeHoursQueueImpl.java are not covered by your spec tests? Why are those lines hard to cover with a spec test?
  2. Did you use AI assistance on this assignment? If yes, which tool(s)?
  3. If you used AI, which parts of the assignment did you use it for?
  4. If you used AI, what's one thing it helped with, if any?
  5. If you used AI, what's one thing it got wrong, or that you had to correct, if any?
  6. Anything else you would like us to know about how this assignment assignment went for you?

Submission

Submit the following files to the Homework 5 assignment on Gradescope:

  • OfficeHoursQueueImpl.java
  • OfficeHoursQueueSpecTest.java
  • OfficeHoursQueueImplTest.java
  • OfficeHoursTerminalApp.java
  • REFLECTION.txt

You can either upload these files individually on Gradescope, or run make submission to bundle them into a submission.zip and upload that.

You should not modify or submit OfficeHoursQueue.java.

We have set up a Gradescope autograder that will compile and run your code. It will run your tests on your own code and show you the results. It will also run one very basic staff test that makes sure you have implemented the zero-argument constructor for the queue ADT. Passing all the autograder tests does not guarantee your code is correct or high quality.