Homework 6: Handed out: 3/11/99; Due: 4/1/99
Note: This assignment involves programming, which will have to be done using J++ in the CSUGLab. Even if you originally use another variant of Java for your program, make sure it runs in the CSUGLab.
As usual, you can discuss this assignment with anyone you like, but you must write it up yourself.
The purpose of this assignment is to use hash tables and heaps to solve some interesting problems efficiently. It is also to emphasize that although space is often plentiful it should not be wasted without reason. Other goals include learning to use standard libraries and writing polymorphic data structures.
The following two files contain the entire student directories for Cornell University and Ithaca College, respectively:
I want to know which addresses have the most Cornell students living at them. This should be done in time O(n log m) assuming hashing behaves, where n is the number of students and m is number of most-common-addresses asked for. I also want to know what addresses have both Cornell students and Ithaca students living at them. This should be done in time O(n) where n is the number of total students, assuming hashing behaves. Space requirements are discussed in more detail below.
You have 3 main things to write, all static methods in the
provided class called BigHouses.
printBigHousesOnePass which solves the
most-common-address problem while looking at the input
file only once. printBigHousesTwoPass which solves the
most-common-address problem while looking at the input
file twice. printIntersection which solves the
addresses-with-people-from-each problem while looking at
each input file only once. The first two methods take 3 arguments: the name of the file
to be used as input, a value for m (the number of
most-common-addresses desired), and a PrintWriter to
which output should be sent. The last method takes 3 arguments:
the two input file names, and a PrintWriter object.
You should use the Hashtable class provided by
the java.util library. You will also need a Heap;
you should write your own. Your Heap class should be
polymorphic over different kinds of objects that have integer
keys. That means your Heap class should be able to
store any instance of any class that implements the Heapable
interface. Your Heap is being used as a priority queue and should
implement the priorityQueueInterface.
Here are more specific requirements for each part:
printBigHousesOnePass
15 YELLOW CARTOONS ROAD, SPRINGFIELD
HOMER SIMPSON
MARGE SIMPSON
BART SIMPSON
LISA SIMPSON
MAGGIE SIMPSON
ITCHY
SCRATCHY
100 STONE STREET, ITHACA, NY 14850
FRED FLINTSTONE
WILMA FLINTSTONE
BAM BAM
printBigHousesTwoPass printIntersection You need to write a 1 - 3 page lab report. Your report should contain at least the following:
Create a local folder with your NetID (your login) as its name. Set the permissions everyone can read it. Then copy your project folder containing all .java, .class, and MS Visual J++ files into the folder \\goose\courses\CS410\A2\Submissions
If you make a mistake and wish to resubmit, submit with a
number after your netid.
For example jjj21_1. We will read the code with the highest
number.
For maintaining a list of names, feel free to use Java's Vector
class. A Vector holds Objects, so you
have to cast anything you take out of a Vector. The Hashtables
are the same way, and your Heaps will be similar, so
you will be doing quite a bit of casting.
Do not bother providing a buildHeap method in your Heap
class; this is not an efficiency bottleneck for this assignment.
You should, however, provide methods min() and extractMin()
for efficiency reasons. You must also provide the method heapify(),
for obvious reasons.
START EARLY. This assignment is substantially longer than the first programming assignment.
The input files are in a very simple format. There is one name
or address per line. It alternates name, address, name, address,
etc. The name corresponds to the address on the following line.
The provided code has a method that takes a file name and returns
a BufferedReader object. This object has a readLine()
method which returns a String which is the next line
of the file. It returns null after the end-of-file
has been reached.
For output in your methods, all you have to do is call the println(String
s) method of the Printwriter object passed to
the methods.
The methods described above could throw an IOException.
Hence the methods you are writing also declare that they may
throw such an exception. You should not catch such exceptions.
If you are using a version of Java that doesn't have BufferedReader,
it should be simple enough to write your own readLine()
method for an input object.
Don't forget that your methods should work for any files in the format described above. Only the main method should explicitly mention the files being used.
We assume that two addresses are equal if and only if they are identical Strings. Hence the following are all different addresses as far as we're concerned:
Style - 10%
Write-up - 30%
Code - 60%