COS 226 Programming Assignment 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. What you have to do is abide by the specified bounds on resources (time, space). So, before you begin to write the code, make sure that your data structure will achieve the required resource bounds.

How serious are you about not calling any library function other than Std* or Integer.parseInt()? You'll receive a substantial deduction. Of course, you may (and will need to) import the java.util.Iterator interface.

If a client creates two randomized queue iterators, should they return the items in the same order? No, each should return them in random order, independent of the other.

What is meant by uniformly at random? If there are N items in the 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 elements in random order? Use StdRandom.shuffle(), which takes linear time. For reference, the shuffling algorithm is described on p. 93 of Introduction to Programming in Java.

What should my iterator do if the deque is structurally modified at any time after the iterator is created (and before it is does 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 ConcurrentModificationException as soon as this happens.

What's the wrapper type for char? Character.

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 testing the API methods.

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 generic array creation. However, you will lose a substantial number of points if your programs produce such warnings unnecessarily. In particular, both client programs should compile without warnings.

Do I need to make my nested class variables private since checkstyle gives a warning? No (but there's no harm in doing so). The access modifiers of the nested class' instance variables are irrelevant—regardless of their access modifiers, they 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: if k is negative or larger than the number of strings on standard input, throw an exception.

What assumptions can I make about the input to Palindrome? It can be any sequence of characters. Of course, if the input contains a character other than an A, C, T, or G, 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. We will test on a machine where echo passes the empty string to your program.

Testing and Submitting

Submission.   Be sure to click the "Check All Submitted Files" button to verify that you submitted all of the required files and that they compile cleanly (modulo the expected warning when creating an array of generics).

Style and bug checkers. Our script uses Checkstyle (and the configuration file checkstyle-cos226.xml) and FindBugs (and the exclusion filter findbugs-cos226.xml) to analyze your code. Eclipse users: there are plugins for checkstyle and findbugs that you can use directly with your IDE. The appearance of warning messages does not necessarily lead to a deduction (and, in some cases, it does not even indicate an error). If you don't understand a warning message, ask a staff member to explain.

Possible Progress Steps

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

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

  2. Stacks and queues. Review the code we used in lecture for generic stacks and queues. The code is available for review in Section 1.3 of Algorithms, 4th edition booksite.

Kevin Wayne