Programming Assignment 2 Checklist: Randomized Queues and Deques

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 external library functions (other than those that are specifically permitted)? 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.

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.

What does"uniformly at random" mean? 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).

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.

Can repeated calls to sample() in a randomized queue return the same item more than once? Yes, since you are sampling without removing the item. This is also known as "sampling with replacement."

Should two iterators to the same randomized queue return the items in the same order? No, each iterator should have a different random order. This is what "independent iterators" means.

Why is it called a randomized queue if the items are not removed in FIFO? This is a common name used in queueing theory.

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?

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:

You should not receive any other compiler warnings on this assignment (and you should not receive any compiler warnings on any other assignment).

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 modifier, it can be accessed anywhere in the file. (Of course, the enclosing class' instance variables should be private.)

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.

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.

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

Test intermixed sequence of operations. Sometimes you want to test two methods in isolation, as above. But, you also need to make sure that all of the methods work together with one another.

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.

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.

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

Getting started. Review Section 1.3 of the textbook for generic stacks and queues with iterators. If you adapt our code, you must include a citation to the original source from either the textbook or the booksite.

Make sure you understand the performance requirements for both Deque and RandomizedQueue. They are summarized in the table below. Every detail in these performance requirements is important. Do not proceed until you understand them.

Deque Randomized Queue

Non-iterator operations Constant worst-case time Constant amortized time

Iterator constructor Constant worst-case time linear in current # of items

Other iterator operations Constant worst-case time Constant worst-case time

Non-iterator memory use Linear in current # of items Linear in current # of items

Memory per iterator Constant Linear in current # of items

Decide whether you want to use an array, linked list, or your own data structure. This choice should be made based on the performance requirements discussed above. You may make different choices for Deque and RandomizedQueue. Make sure that your memory use is linear in the current number of items, as opposed to the greatest number of items that has ever been in the data structure since its instantiation. If you're using a resizing array, you must resize the array when it becomes sufficiently empty. You must also take care to avoid loitering anytime you remove an item.
Use our example programs as a guide when implementing your methods. There are many new ideas in this programming assignment, including resizing arrays, linked lists, iterators, the foreach keyword, and generics. If you are not familiar with these topics, our example code should make things much easier. ResizingArrayStack.java uses a resizing array; LinkedStack.java uses a singly-linked list. Both examples use iterators, foreach, and generics.

	Deque	Randomized Queue
Non-iterator operations	Constant worst-case time	Constant amortized time
Iterator constructor	Constant worst-case time	linear in current # of items
Other iterator operations	Constant worst-case time	Constant worst-case time
Non-iterator memory use	Linear in current # of items	Linear in current # of items
Memory per iterator	Constant	Linear in current # of items

A video is provided for those wishing additional assistance. Be forewarned that video was made in early 2014 and is somewhat out of date. For example the API has changed.