CS 3345.004. Data structures and algorithm analysis
Fall 2018
Assignment 3
Sep 5, 2018

Due: Wed, Sep 12:  8:30 AM (in class or on elearning).


1. What is the running time of the following two programs on a linked list with n elements:

   (a) for(x: list) { print x }  /* using the iterator */
	/* same as:  it = list.iterator();  while(it.hasNext()) { print it.next() } */

   (b) for(i=0; i<list.size(); i++) { print list.get(i) }


Optional problems:

2. Write pseudocode for an array list implementation of a list.
   Try to write the code on your own, without seeing the book.

3. Write pseudocode for an array implementation of a bounded-sized queue (BoundedQueue<T>)
   with the following operations:

   BoundedQueue(int size): Constructor for queue of given size
   boolean offer(T x):  add a new element x at the rear of the queue
                        returns false if the element was not added because the queue is full
   T poll():            remove and return the element at the front of the queue
                        return null if the queue is empty
   T peek():            return front element, without removing it (null if queue is empty)
   int size():          return the number of elements in the queue
   boolean isEmpty():   check if the queue is empty
   void clear():        clear the queue (size=0)
   void toArray(T[] a): fill user supplied array with the elements of the queue, in queue order