Specification Here is the programming assignment ...

Question

Specification
Here is the programming assignment
specification
that describes the assignment requirements.

Web Submission
Submit a zip file named queues.zip that contains only the three source files Deque.java, RandomizedQueue.java, and Permutation.java.

Assessment Report
See the
Assessment Guide
for details on how to interpret the assessment report.

Thought

Considering Java implementation

I believe the assignment asks for a generic randomized queue and deque, focusing on permutation via sampling without replacement. I'll aim to develop Java implementations that match the required APIs for these structures, handling things like iteration order, exceptions for invalid operations, and using provided input/output classes.

Clarifying implementation details

I need to stick to the assignment requirements: using a doubly-linked list for the Deque and a resizing array for the RandomizedQueue. For Permutation, it expects the use of RandomizedQueue to enqueue all strings and then dequeue k items, which may involve storing them all. There's extra credit for minimizing memory usage, though.

Focusing on code requirements

It's crucial to ensure the code matches the Coursera assignment's autograder criteria. That means implementing generics for Deque and RandomizedQueue, having them be iterable, and keeping operations efficient. I'll make sure to follow the guidelines, including correct exception handling and adding required methods, then package the files into a zip as requested.

Plan for project deliverables

We need to create code and package it into a zip file. I'll make sure to avoid web.run, as it’s not relevant here. The provided Java code must compile correctly with the necessary library imports, but we can't use the Princeton algs4 library for Deque and RandomizedQueue, except for specific exceptions and iterator features.

Thought for 36s

Answer

Got it — I’ve packaged clean, spec-friendly implementations for Deque, RandomizedQueue, and the Permutation client.

Download queues.zip

Quick notes:

Deque.java: doubly-linked list; addFirst/addLast/removeFirst/removeLast are all $O(1)$ . Iterator goes front→back. Proper argument/underflow checks; no loitering.
RandomizedQueue.java: resizing array; dequeue() removes a uniformly random item via swap-with-last; sample() peeks at a random item; iterator yields items in independent random order using StdRandom.permutation(n). Includes all required exceptions and amortized $O(1)$ ops.
Permutation.java: reads k from args, enqueues all tokens from StdIn, prints exactly k strings by dequeuing from the randomized queue (each printed once, uniformly at random).

File list inside the zip (as requested): Deque.java, RandomizedQueue.java, Permutation.java. If you want a memory-lean Permutation (reservoir sampling) or extra unit tests, say the word and I’ll drop them in.