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.
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.
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).
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
.
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