CS 3500 Assignment #10
Assigned:  Wednesday, 28 November 2012
Due:  Tuesday, 4 December 2012

The purposes of this assignment are:

 * to benchmark FMap<K,V> against HashMap<K,V> and TreeMap<K,V>
 * to emphasize the importance of asymptotic (big-O) complexity
 * to demonstrate reusable implementations of standard data structures

For this assignment, you will use a benchmark written by the
instructor to compare the performance of your implementation
of FMap<K,V> against the reusable standard implementations of
HashMap<K,V> and TreeMap<K,V> from the java.util package.

You will run the instructor's benchmark on a machine of your
choosing, subject to two restrictions listed below.  You will
copy the output of that benchmark into a written memo, in the
format described below, and you will submit a paper copy of
that memo at the beginning of class on Tuesday, 4 December.

You will also submit your code for FMap<K,V> via the usual
process for submitting assignments electronically.  That code
will not be graded, but it will be tested.  (The main purpose
of this testing is to deter dry-labbing, which is a form of
scientific misconduct.)

Collaboration between students is forbidden on this assignment.
You are responsible for keeping your code and your benchmark
results hidden from all other students.

--------------------------------------------------

On Tuesday, 4 December, at the beginning of class, you will
turn in the paper copy of your memo, in the format described
below.

In addition to the paper memo, you will submit your code for
the implementation of FMap<K,V> that you benchmarked to obtain
the results stated in your memo.  You should take great care
to submit exactly the same implementation of FMap<K,V> that
you benchmarked.  Submit your Java code for FMap<K,V> using
the submit script as documented on the course's main assignments
web page, http://www.ccs.neu.edu/course/cs3500wc/assignments.html

Your file of Java code should begin with a block comment that lists
    1.  Your name.
    2.  Your email address.
    3.  Any remarks you wish to make to the instructor.

Most of your grade will depend on how well you follow the
instructions for writing your memo.  Your grade will also
depend on whether your implementation produces correct output
and on whether the Java code you submit electronically
is the same as the code you benchmarked to obtain the results
stated in your memo; dry-labbed memos will not receive any
credit at all.

Late or incorrectly submitted assignments will be heavily
discounted, if they are accepted at all.

--------------------------------------------------

You are given three files in /course/cs3500wc/Assignments/A10:

    Visitor.java
    BenchFMap.java
    thucydides.txt

The Visitor.java file is the same as in previous assignments.

The BenchFMap.java file contains the benchmark program you
will use to measure the performance of your implementation of
the FMap<K,V> abstract data type.

thucydides.txt contains (a possibly truncated version of)
Richard Crawley's translation of Thucydides's History of the
Peloponnesian War.  Crawley's translation was completed in 1874,
and is now in the public domain.  We are using it as a source
of real-world data, whose characteristics lie somewhere in
between the idealized average case and the worst case.

To run the benchmark, you will need a computer that (1) supports
a version of Java similar to the version installed on the CCIS
Linux machines, and (2) is not being used for any purpose other
than running the benchmark.  (If the machine were being used by
other people or to run other programs at the same time, then the
other users or programs would probably have some influence on
the benchmark timings.)

Using your selected machine, compile the BenchFMap.java program
along with your FMap.java code.  Then run the BenchFMap program
using thucydides.txt as input.  Copy and paste the output of the
BenchFMap program into your memo as shown below.

If your implementation of FMap<K,V> is slow, as it would be if
your implementation always represents FMap values by association
lists, then the benchmark will take a long time to run, and you
will probably have to expand the stack segment from its default
value.  If you need to increase the size of the stack segment,
then it is your responsibility to figure out how to do that on
your chosen machine.  On CCIS Linux machines, you can run the
benchmark with a 20 megabyte stack segment as follows:

    % java -Xss20M BenchFMap thucydides.txt

If your implementation of FMap<K,V> uses binary search trees or
red-black trees, then the benchmark will probably run so quickly
that its timing would be unreliable unless you tell the benchmark
program to repeat each part of the benchmark multiple times.  To
run each part of the benchmark 100 times, use the following
command line:

    % java BenchFMap thucydides.txt 100 100

--------------------------------------------------

Format of your memo.

Your memo should follow this outline:

    <your name>
    <your email address>

    <the command line you used to run the benchmark>

    <the output produced by the benchmark program>

    Representation: <see below>

    Machine: <see below>

Please describe only the representation that your implementation
of FMap<K,V> uses when a Comparator is provided as an argument
to emptyMap.  To describe that representation, please use one
of the following phrases:

    association list
    binary search tree
    red-black tree
    other

If you write "other", please explain your representation in
more detail.

To describe your machine, please use the following example as
a guide:

    Machine:
        Dell Optiplex 745
        Intel Pentium D (dual core, 64-bit) @ 3.4 GHz
        3.9 GB RAM
        Linux (Ubuntu release 9.10)
        Java version 1.6.0_20

--------------------------------------------------