COS 226 Programming Assignment Checklist: Randomized Queues and Dequeues

Frequently Asked Questions

What's a checklist? The assignment checklists are meant to supplement the assignment, and clear up any confusing points. They will also provide brief hints on getting started. They also include links to sample data files, reference solutions, and readme template files. Be sure to read the checklist before each assignment.

Is there anything else I should do before getting started? Please read the Assignments Page, including the collaboration policy, lateness policy, and submission system instructions if you have not done so already. The programming assignments will require a good deal of time. The final source code may not be that long, but creating and debugging the code is a serious time commitment. It would be a mistake to wait until after Tuesday precept to start your assignments. You may be able to ask more meaningful questions in precept if you already have worked on the program enough to know what the real difficult issues are.

What Java programming environment should I use? You are free to choose your own. We recommend DrJava and the command-line, which is what most of you used in COS 126. For instruction, go to the first paragraph of Section 1.1 of Introduction to Programming. You will also need to use the command line on your system. You can review how to do this in Section 1.5 of Introduction to Programming.

How should I read from standard input? In this course you will use our home-brewed library to read text from standard input. For those of you that didn't take COS 126, read Section 1.5 of Introduction to Programming to learn how to use it. Note that there is a DrJava bug that prevents StdIn.isEmpty() from returning true, so you must use the command line to execute your program.

How should I generate a pseudo-random integer between 0 and n-1? You may use the following function for this assignment.

public static int random(int n) {
    return (int) (Math.random() * n);
Alternatively, you can use java.util.Random by delcaring an instance variable named random of type Random and invoking random.nextInt(n) as needed.

What should my program do if remove() is called when the queue is empty? You should throw a RuntimeException with an underflow error message. See for an example.

What should Subset do if the command-line parameter k is negative? Larger than the number of string read in? If k is negative, it should either print nothing or throw an exception. If k is too big, it should either print all of the strings in random order or throw an exception. In general, if we don't specify a corner case, you are free to handle it in any "reasonable" manner provided you document what it is.

Can you give me some examples of Watson-Crick palindromes? Yes: "AAAACGTTTT, "ATATATAT", and "". No: "AAAA", "AAAAGTTTT", "ATAATA", "ZZZZ" and "AaTT".

What is meant by uniformly at random? If there are N elements in the queue, then you should choose each one with probability 1/N, up to the randomness of random() or random.nextInt(), independent of past decisions.

What's the wrapper type for char? Character.

Can I make up my own names for the names of the classes and methods? No.

Can I add extra methods to the Deque or RandomizedQueue? Yes, provided they are generally applicable to a variety of applications, e.g., a method size() that returns the number of items currently in the data structure.

How serious are you about declaring only one variable in each client? Not entirely. You may declare O(1) extra variables provided it makes your program easier to read.

How should I format and comment my code? Here are some style guidelines that your grader will appreciate.

The compiler says that my program uses unchecked or unsafe operations and to recompile with -Xlint:unchecked for details. Usually this means you did a potentially unsafe cast. When implementing a stack with an array, this is unavoidable since Java does not allow arrays of generic types.

Testing and Submitting

Submission.   After you have submitted all of the required files (, RandomizedQueue,,, and readme.txt) the "Run Script" button on the submission system will appear. Be sure to hit the button and check that you submitted the right files and they compile cleanly.

Our script uses Checkstyle and FindBugs to analyze your code. The appearance of warning messages does not necessarily indicate an error or lead to a deduction.

Readme.   Use the following readme file template and answer all questions.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

  1. Installing a Java programming environment. Follow the instructions from the Hello World assignment from COS 126 to install Java 1.5 on your system. If you have a previous version of Java, we recommend uninstalling it before upgrading. To develop your programs, we recommend DrJava and the command line. If you use an IDE (integrated development environment), be sure that you can use command-line arguments, read from standard input, and redirect standard input and output.

  2. Getting started. Download the directory queues to your system. It contains the file that you will use to read in input characters from standard input.

  3. Stacks and queues. Review the code we used in lecture for generic stacks and queues. See Section 4.3 of Introduction to Programming in Java.

Kevin Wayne