Programming Assignment 2 Checklist: Randomized Queues and Dequeues

Frequently Asked Questions

Should I use arrays or linked lists in my implementations? In general we don't tell you how to implement your data structures—you can use arrays, linked lists, or maybe even invent your own new structure provided you abide by the specified time and space requirements.

How serious are you about not calling any external library function other than those in stdlib.jar? You will receive a substantial deduction. The goal of this assignment is to implement data types from first principles, using resizing arrays and linked lists—feel free to use java.util.LinkedList and java.util.ArrayList on future programming assignments. We also require you to use StdIn (instead of java.util.Scanner) because we will intercept the calls to StdIn in our testing. Of course, importing java.util.Iterator and java.util.NoSuchElementException are fine.

Can I add extra public methods to the Deque or RandomizedQueue APIs? Can I use different names for the methods? No, you must implement the API exactly as specified. The only exception is the main() method, which you should use for unit testing.

What is the API for Subset? It should contain only a main() method—do not include other public methods or public constructors. It should require only 5-10 lines of code, so making it an object is overkill.

What is meant by uniformly at random? If there are N items in the randomized queue, then you should choose each one with probability 1/N, up to the randomness of StdRandom.uniform(), independent of past decisions. You can generate a pseudo-random integer between 0 and N-1 using StdRandom.uniform(N) from the library.

Given an array, how can I rearrange the entries in random order? Use StdRandom.shuffle()—it implements the Knuth shuffle discussed in lecture and runs in linear time. Note that depending on your implementation, you may not need to call this method.

What should the next() method return if the iterator has no more items? According to the API for java.util.Iterator, it should throw a java.util.NoSuchElementException.

What should my deque (or randomized queue) iterator do if the deque (or randomized queue) is structurally modified at any time after the iterator is created (but before it is done iterating)? You don't need to worry about this in your solution. An industrial-strength solution (used in the Java libraries) is to make the iterator fail-fast: throw a java.lang.ConcurrentModificationException as soon as this is detected.

Why does the following code lead to a generic array creation compile-time error when Item is a generic type parameter?

Item[] a = new Item[1];
Java prohibits the creation of arrays of generic types. See the Q+A in Section 1.3 for a brief discussion. Instead, use a cast.
Item[] a = (Item[]) new Object[1];
Unfortuantely, this leads to an unavoidable compiler warning.

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 generic stack with an array, this is unavoidable since Java does not allow generic array creation. For example, the compiler outputs the following warning with

% javac
Note: uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

% javac -Xlint:unchecked warning: [unchecked] unchecked cast
found   : java.lang.Object[]
required: Item[]
        a = (Item[]) new Object[2];
                     ^ warning: [unchecked] unchecked cast
found   : java.lang.Object[]
required: Item[]
        Item[] temp = (Item[]) new Object[capacity];
2 warnings

You should not make any other casts.

Checkstyle complains that my nested class' instance variables must be private and have accessor methods that are not private. Do I need to make them private? No, but there's no harm in doing so. The access modifier of a nested class' instance variable is irrelevant—regardless of its access modifiers, it can be accessed anywhere in the file. (Of course, the enclosing class' instance variables should be private.)

Can a nested class have a constructor? Yes.

What assumptions can I make about the input to Subset? Standard input can contain any sequence of strings. You may assume that there is one integer command-line argument k and it is between 0 and the number of strings on standard input.

What's the wrapper type for char? Character.

What assumptions can I make about the input to Palindrome? It can be any sequence of characters. Of course, if the input contains any character other than an 'A', 'C', 'T', or 'G' (including any lowercase character or whitespace character), it cannot be a Watson-Crick complemented palindrome.

I'm using Windows and my program doesn't work when I type echo | java Palindrome. What could be wrong? On Windows, the echo command without an argument outputs "ECHO is on", so this becomes the input to your program; instead you can use echo. | java Palindrome. We will test on a machine where echo | java Palindrome passes the empty string to your program.

Will I lose points for loitering? Yes. See p. 137 of the textbook for a discussion of loitering. Loitering is maintaining a useless reference to an object that could otherwise be garbage collected.


  1. We strongly recommend that you develop unit tests as you write each method and constructor to allow for testing. As an example for Deque, you know that if you call addFirst() with the numbers 1 through N in ascending order, then call removeLast() N times, you should see the numbers 1 through N in ascending order. As soon as you have those two methods written, you can write a unit test for these methods. In addition use randomized unit tests (which we employ heavily in our correctness testing). We recommend that you create a client class with a name like TestDeque, where each unit test is a method in this class.

  2. Don't forget to test your iterator. And make sure to test that multiple iterators can be used simultaneously. You can test this with a nested foreach loop. The iterators should operate independently of one another.

  3. Make sure to test what happens when your data structures are emptied. One very common bug is for something to go wrong when your data structure goes from non-empty to empty and then back to non-empty. Make sure to include this in your tests.

  4. Don't rely on our automated tests for debugging. As suggested above, write your own unit tests; it's good practice.
Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps. These same steps apply to each of the two data types that you will be implementing.