|
|
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 provide you abide by the specified time and space requirements. 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 will receive a substantial deduction. Of course, importing the java.util.Iterator interface is fine.
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 StdRandom.java library.
Given an array, how can I rearrange the entries 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 the remove() method in my iterator do if it is not supported? What should the next() method return if the iterator has no more items? According to the API for the Iterator interface, remove() should throw an UnsupportedOperationException and next() 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 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.
Why does the following code lead to a generic array creation compile-time error when Item is a generic type parameter?
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 = new Item[1];
Unfortuantely, this leads to an unavoidable compiler warning.Item[] a = (Item[]) new Object[1];
I'm using a linked list and don't like dealing with these special cases when the list is empty or almost empty. Is there some way to simplify them? Yes. One common method is to include sentinel nodes. A sentinel node is just a special node created by the constructor which is never removed, and which contains dummy data which is never used. The trick is that your head (and tail, if applicable) pointers always point at these special sentinel nodes, even if the list is empty. In other words, the head (and tail) pointers are never null, thus avoiding the need to check to see if the head (or tail) is null.
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 ResizingArrayStack.java:
% javac ResizingArrayStack.java
Note: ResizingArrayStack.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
% javac -Xlint:unchecked ResizingArrayStack.java
ResizingArrayStack.java:25: warning: [unchecked] unchecked cast
found : java.lang.Object[]
required: Item[]
a = (Item[]) new Object[2];
^
ResizingArrayStack.java:36: warning: [unchecked] unchecked cast
found : java.lang.Object[]
required: Item[]
Item[] temp = (Item[]) new Object[capacity];
^
2 warnings
However, you will lose points if your programs makes unnecessary casts. In particular, both client programs should compile without warnings.
Checkstyle complains that my nested class' instance variables must be private and have accessor methods.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 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.
When I am asked to give an answer using tilde notation or order-of-growth notation, should I include the leading coefficient and the lower order terms? By definition, tilde notation includes the leading coefficient but discards the lower order terms; order of growth notation discards both the leading coefficient and the lower order terms. See pp. 178-179 of the textbook.
|
|
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.xml) and FindBugs (and the configuration file findbugs.xml) to analyze your code.
Note that Checkstyle inspects the source code; Findbugs inspects the compiled code.% checkstyle HelloWorld.java % checkstyle *.java % findbugs HelloWorld.class % findbugs Deque*.class
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.