Crypto Week 2 Programming Assignment 2

  虽然是春节,但Coursera竟然没有任何让人休息的意思,课程还是接着上…这周的题目看起来比较简单,但是实际上问题一堆,我从上午2:30开始听Lecture,大概5点就把Quiz搞定了,但是这个ProgrammingAssignment却让我一直折腾到现在… 当然了,更多的原因不是因为我这代码有问题,是Princeton的JavaJDK貌似OutOfMemoryException了!看来Princeton也会出现这样那样的问题啊…

题目

Programming Assignment 2: Randomized Queues and Deques

Write a generic data type for a deque and a randomized queue.The goal of this assignment is to implement elementary datastructures using arrays and linked lists, and to introduce you togenerics and iterators.

Dequeue. A double-ended queue or deque(pronounced "deck") is a generalization of a stack and a queue thatsupports inserting and removing items from either the front or theback of the data structure. Create a generic data type that implements the following API:

public class Deque implements Iterable {     public Deque() // construct an empty deque     public boolean isEmpty() // is the deque empty?     public int size() // return the number of items on the deque     public void addFirst(Item item) // insert the item at the front     public void addLast(Item item) // insert the item at the end     public Item removeFirst() // delete and return the item at the front     public Item removeLast() // delete and return the item at the end     public Iterator iterator() // return an iterator over items in order from front to end }

Throw a if the clientattempts to add a null item; throw a if the client attempts toremove an item from an empty deque; throw a if the clientcalls the method in the iterator; throw a if the client calls the method in the iterator and there are no more itemsto return.

Your deque implementation should support each deque operation inconstant worst-case time and use space proportional to thenumber of itemscurrently in the deque. Additionally, youriterator implementation should support the operations and (plus construction) inconstant worst-case time and use a constant amount of extra spaceper iterator.

Randomized queue. A randomized queue is similarto a stack or queue, except that the item removed is chosenuniformly at random from items in the data structure. Create ageneric data type that implements thefollowing API:

public class RandomizedQueue implements Iterable {     public RandomizedQueue() // construct an empty randomized queue     public boolean isEmpty() // is the queue empty?     public int size() // return the number of items on the queue     public void enqueue(Item item) // add the item     public Item dequeue() // delete and return a random item     public Item sample() // return (but do not delete) a random item     public Iterator iterator() // return an independent iterator over items in random order }

Throw a if the clientattempts to add a null item; throw a if the client attempts tosample or dequeue an item from an empty randomized queue; throw a if the clientcalls the method in the iterator; throw a if the client calls the method in the iterator and there are no more itemsto return.

Your randomized queue implementation should support eachrandomized queue operation (besides creating an iterator) inconstant amortized time and use space proportional to thenumber of itemscurrently in the queue. That is, anysequence ofM randomized queue operations (starting froman empty queue) should take at mostcM steps in the worstcase, for some constantc. Additionally, your iteratorimplementation should support construction in time linear in thenumber of items and it should support the operations and in constant worst-case time;you may use a linear amount of extra memory per iterator. The orderof two or more iterators to the same randomized queue should bemutually independent; each iterator must maintain its ownrandom order.

Subset client. Write a client program that takes a command-line integerk,reads in a sequence ofN strings from standard input using, and prints out exactlyk ofthem, uniformly at random. Each item from the sequence can beprinted out at most once. You may assume thatk ≥ 0 and nogreater than the number of string on standard input.

% echo A B C D E F G H I | java Subset 3 C G A % echo AA BB BB BB BB BB CC CC | java Subset 8 BB AA BB CC BB BB CC BB % echo A B C D E F G H I | java Subset 3 E F G
Your client should use only constant space plus one object eitherof type or of type; usegenerics properly to avoid casting and compiler warnings. It shouldalso use time and space proportional to at mostN in theworst case, where N is the number of strings on standardinput. (For an extra challenge, use space proportional tok.) It should have the following API.
public class Subset {     public static void main(String[] args) }
Deliverables. Submit only ,, and. We willsupply. You may not call any library functionsother than those in and.

分析

   这题吧,难点不在于实现本身,难点在于Memory,也就是说一定要清除一个没有用的Object的任何引用才视为这个内存已经被释放了。在本例中,Deque类要注意Node.previous以及Node.next,在拿走一个元素后相关的previous以及next都要设置为null才可以。
   在RandomizedQueue中,提取的元素要求是随机提取的,所以不能使用链表(提取一个元素的复杂度为O(n)),要使用数组实现。实际上,因为是随机提取元素,不一定非要用queue的思路,完全可以用bag的思路来,元素顺序是可以任意排列的(反正提取的时候也是随机提取)。

代码

1. Deque.java

public class Deque<Item> implements Iterable<Item> {     private int N;         // number of elements on queue     private Node first;    // beginning of queue     private Node last;     // end of queue     // helper linked list class     private class Node {         private Item item;         private Node next;         private Node previous;     }             public Deque() {         first = null;         last  = null;         N = 0;     }             public boolean isEmpty() {         return N == 0;     }             public int size() {         return N;         }         // insert the item at the front     public void addFirst(Item item){         if (item == null){             throw new java.lang.NullPointerException();         }         Node oldfirst = first;         first = new Node();         first.item = item;         first.previous = null;         if (isEmpty()){             last = first;             first.next = null;         }else{             oldfirst.previous = first;             first.next = oldfirst;         }         N++;     }         // insert the item at the end     public void addLast(Item item){         if (item == null){             throw new java.lang.NullPointerException();         }         Node oldlast = last;         last = new Node();         last.item = item;         last.next = null;         if (isEmpty()){             first = last;             last.previous = null;         }else{             oldlast.next = last;             last.previous = oldlast;         }         N++;     }         // delete and return the item at the front     public Item removeFirst(){         if (isEmpty()) throw new java.util.NoSuchElementException();         Item item = first.item;         first = first.next;         N--;         if (isEmpty()){             last = null;             first = null;         }else{             first.previous = null;         }         return item;     }         // delete and return the item at the end     public Item removeLast(){         if (isEmpty()) throw new java.util.NoSuchElementException();         Item item = last.item;         last = last.previous;         N--;         if (isEmpty()){             last = null;             first = null;         }else{             last.next = null;         }         return item;     }             public java.util.Iterator<Item> iterator()  {         return new ListIterator();     }     // an iterator, doesn't implement remove() since it's optional     private class ListIterator implements java.util.Iterator<Item> {         private Node current = first;         public boolean hasNext()  { return current != null;                     }         public void remove()      { throw new java.lang.UnsupportedOperationException();  }         public Item next() {             if (!hasNext()) throw new java.util.NoSuchElementException();             Item item = current.item;             current = current.next;             return item;         }     } }
2. RandomizedQueue.java public class RandomizedQueue<Item> implements Iterable<Item> {     private Item[] q;            // queue elements     private int N = 0;           // number of elements on queue         // cast needed since no generic array creation in Java     public RandomizedQueue() {         q = (Item[]) new Object[2];     }         public boolean isEmpty(){         return N == 0;        }         public int size(){         return N;     }         // resize the underlying array     private void resize(int max) {         assert max >= N;         Item[] temp = (Item[]) new Object[max];         for (int i = 0; i < N; i++) {             temp[i] = q[i];         }         q = temp;     }         public void enqueue(Item item) {         if (item == null){             throw new java.lang.NullPointerException();         }         // double size of array if necessary and recopy to front of array         if (N == q.length) resize(2*q.length);   // double size of array if necessary         q152 = item;                        // add item         N++;     }         public Item dequeue() {         if (isEmpty()) throw new java.util.NoSuchElementException();         int index = StdRandom.uniform(N);         Item item = q[index];         if (index != N-1){             q[index] = q[N-1];         }         q[N-1] = null;                            // to avoid loitering         N--;         if (N > 0 && N == q.length/4) resize(q.length/2);         return item;     }     // return (but do not delete) a random item     public Item sample(){         if (isEmpty()) throw new java.util.NoSuchElementException();         int index = (StdRandom.uniform(N));         return q[index];     }         public java.util.Iterator<Item> iterator() { return new ArrayIterator(); }     // an iterator, doesn't implement remove() since it's optional     private class ArrayIterator implements java.util.Iterator<Item> {         private Item[] tempItem = (Item[]) new Object[q.length];                 private int tempN = N;         public boolean hasNext()  { return tempN != 0;                               }         public void remove()      { throw new UnsupportedOperationException();  }                 public ArrayIterator(){             for (int j=0; j<q.length; j++){                 tempItem[j] = q[j];             }         }                 public Item next() {             if (!hasNext()) throw new java.util.NoSuchElementException();             int index = (StdRandom.uniform(tempN));             Item item = tempItem[index];             if (index != tempN-1){                 tempItem[index] = tempItem[tempN-1];             }             tempItem[tempN-1] = null;                            // to avoid loitering             tempN--;             return item;         }     }         public static void main(String[] args) {         RandomizedQueue<String> q = new RandomizedQueue<String>();         while (!StdIn.isEmpty()) {             String item = StdIn.readString();             if (!item.equals("-")) q.enqueue(item);             else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");         }         StdOut.println("(" + q.size() + " left on queue)");     } }
3. Subset.java public class Subset {     public static void main(String[] args){         RandomizedQueue<String> q = new RandomizedQueue<String>();         int k = Integer.valueOf(args[0]);         while (!StdIn.isEmpty()) {             String item = StdIn.readString();             q.enqueue(item);         }         while (k > 0){             StdOut.println(q.dequeue());             k--;         }     } }

Чип, который он должен был припаять, упал ему на голову. - Проклятие. Телефон звонил не переставая.

0 thoughts on “Crypto Week 2 Programming Assignment 2

Leave a Reply

Your email address will not be published. Required fields are marked *