CS 112 Summer 2, 2017 -- Homework Five

Due Friday, July 21st at midnight

Introduction

This consists of several programming problems. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):

No Part A this week --- we will return to Part A problems next time!

Problem B.1 (Lab Problem) Java Generics (20 points)

Hand in your files GenericStack.java and GenericPQueue.java from lab on Tuesday, and your file RecursiveGraphics.java from lab on Wednesday.

Problem B.2 (50 points)

For this problem you will create a IntDeque ADT using the circular-buffer technique presented in lecture. Please review the lecture slides before starting this problem.

This ADT has the following interface:

void enqueueFront(int k) -- Insert a new int at the front of the queue; if the queue is full, you must reallocate a bigger array before doing
                            the insertion (algorithm described below). 

int dequeueFront()  --  Remove the int at the front of the queue and return it; if the queue is empty throw a QueueUnderflowException

void enqueueRear(int k) -- Insert a new int at the rear of the queue; if the queue is full, you must reallocate a bigger array (see below).

int dequeueRear()  --  Remove the int at the rear of the queue and return it; if the queue is empty throw a QueueUnderflowException

int size() -- return the number of ints currenting being stored in the queue

isEmpty() -- return true if the size is 0, and false otherwise

String toString() -- Return a String representation of the deque (can be similar to what was done in Lab 05)
  

Dealing with Overflow by Resizing the Array

A simple but effective way to deal with the problem of overflow for array-based data structures such as stacks and queues is to reallocate a larger array and move all the data items over to the new array. This is called resizing, and you should create a method resize() following this pseudo-code:

// Assuming that the data is held in an array A whose length is given by the variable SIZE,
// this method will replace A by an array twice as big, with the same data items.

public void resize() {
    //  allocate an array B twice as big as A
    //  update the variable SIZE to indicate the new maximum size
    //  copy all the elements from A over to B
    A = B;        // replace A with B 
}

This method would be called from inside enqueueFront and enqueueRear if the data structure is full and can not store any more elements. One complication is that the elements in the queue almost certainly will not line up perfectly at the beginning of A (i.e., with the front at A[0]), and so you can't just copy them over to the same locations. So, you would need to do something like this:

B[0]  =  A[front];
B[1] =   next item clockwise around circle from A[front];                    // naturally, you will use nextSlot(front)
....
B[A.length - 1]  =  item at end of queue, which is in fact previous item counter-clockwise around the circle from A[front]
// the rest of B will have 0's. 

and then reset front and next appropriately. This is similar to what you have done in the lab problem, where you had to reset the array to have the elements at the beginning, but in this case you are moving them to an entirely new array.

Requirements and Suggestions

You should start from the template IntDeque.java and MUST satisfy the following requirements for this problem:

You SHOULD do the following while developing your program:

Submit your file IntDeque.java as part of your homework submission for HW05.

 

Problem B.3 Linked List Practice (30 points)

For this problem you must download and complete the template linked here: LinkedListPractice.java. You will have various method stubs to complete. Go through in order and fill in the implementations, following, as always, the testing code in the main method.

 

Submission:

Files to submit:

Make sure that all programs are properly commented, neat and readable, all debugging trace statements are turned off or removed, and verify that you correctly pass all the performance tests in the unit tests.

You will need to follow the style guidelines about comments, especially a header comment, described in the Java Style Guidelines linked at the top of this document. Also, you MUST format your code using the Eclipse Format command. Make sure your program is neat and readable by humans!!!

You will receive a grading penalty if you do not follow these requirements.