CS 112B1 Spring 2012 -- Programming Assignment One

Due Thursday, February 2nd at 10PM

Introduction

This homework consists of several programming problems. I suggest you read each problem carefully and think about your solution for a bit before launching Dr. Java and beginning to type. In addition to the requirements for each problem, you must observe the following requirements (for all programming assignmnets submitted in this course):

Consult the textbook and the Java online documentation as needed.

Problem One: Integer Multisets (20 pts)

For this problem you are going to provide implementations for a simple collection, which can be thought of as a Bag (p.121) that supports deletion, or a Set (p.489) that allows duplicate elements. The interface that specifies this ADT is as follows (and may be found in the file IntMultiset.java on the class web site):

public interface IntMultiset {
   void add(int k);            // insert k into multiset--may produce duplicate versions of k
   void delete(int k);         // delete one instance of k--other instances of k may remain
   boolean contains(int k);    // does k occur in the multiset?
   boolean isEmpty();          // is the multiset empty?
   int size();                 // total number of elements in the multiset (including duplicates)
}

The implementation will use an ordered array of 100 integers. Here are some hints:

int add(int k): Either use a linear scan, or use binary search, to find the location where the new element should be, then move all elements with higher indices over to make room for the new element. Do not worry about overflow.

int delete(int k): Search the array and find an occurrence of k (if it exists) and then move all elements with higher indices down one.

boolean contains(int k): Use binary search to find the element (if it exists);

Submit your code in a file OrderedIntMultiset.java.

Follow all the suggestions in the discussion on Java program structure, in particular, making all class members as private as possible. Your implementation should work with the client program IntMultisetClient.java (on the class web site), which will access your class and tell you what output is expected.

Problem Two: Random Queues (30 pts)

Consider the Random Queue API specified in Problem 1.3.35 in our textbook. First implement this API as a RandomQueue class in a file named RandomQueue.java. Use the hints as specified in the question. You will need to work from a generic array-based Queue implementation -- in the Monday 1/30 lab sections, we will devote much of lab to implementing this (not in the textbook).

Write a test client in RQDriver.java that "shuffles" a standard 52-card deck of playing cards by inserting them into a RandomQueue, and deals out a 13-card bridge hand to each of four players, i.e. prints the contents of the hands to standard output. You will also need a Card class, so define and submit a Card class in Card.java as you see fit (it should at least contain a String member variable and a toString() method).

Problem Three: Analysis (10 pts)

For each of the methods in each of your implementations in Problems 1 and 2, give the worst case running time for a data structure containing N items. Count the number of times you have to "touch" an item (e.g., access it or compare or move it -- just count once for each element, i.e., if you compare and then move it, then that counts as one "touch"). Then answer the question "Why do you think we are unconcerned about whether you use binary search or a linear scan in add and delete?" Submit this as a file PA01.Prob03.txt or PA01.Prob03.pdf.

Problem Four: Josephus problem (15 pts)

Solve the Josepus problem as stated in Problem 1.3.37 in our textbook. Submit the client in a file Josephus.java. Your code should use the Queue API as provided on p. 121.

Test with the Queue code implemented by the booksite, but do not submit the Queue code (we will test against it ourselves).