CSE373—Data Structures and Algorithms
for Nonmajors
Programming Assignment #2
due: Monday,
Overview:
In the previous assignment, the program tried
successive strategies over a continually changing list of cells. The third strategy, the most powerful, was
also the most expensive time-wise. In
this assignment, we address how to keep most of the functionality of DeriveRuleMineStrategy while greatly improving its speed
(at the cost of space).
As I am typing this document right now, my
computer is playing thousands of games of MineSweeper,
recording snapshots of windows of the boards when DeriveRuleMineStrategy
concludes that a cell should be marked or explored. You will have all this data at your disposal –
precomputed – and your task will be to use it instead
of doing the expensive computations of DeriveRuleMineStrategy.
Programming
(40%):
We will use all files from the previous
assignment, and add the following:
·
MineWindow.java – a window on a board;
there exists two sets of these, windows that illustrate Mark rules and windows
that illustrate Explore rules (you need to implement hashCode
here)
·
RecordDeriveRuleMineStrategy – basically DeriveRuleMineStrategy, but it also stores rules that
succeed (mostly for your enjoyment)
·
PrecomputedMineStrategy – this strategy sees if
the current window matches one in the markSet or exploreSet, and if so, returns the appropriate decision
|
Method |
Description |
|
int hashCode() |
Returns
a hash code value for a MineWindow object. |
Quoting Sun’s writeup,
the general contract of hashCode is:
hashCode method
on each of the two objects must produce the same integer result. equals(java.lang.Object)
method, then calling the hashCode
method on each of the two objects must produce distinct integer results.
However, the programmer should be aware that producing distinct integer
results for unequal objects may improve the performance of hashtables. Your hashCode must
satisfy the above contract and should be designed to perform hashing well.
To test your hashCode,
replace the last strategy, which was DeriveRuleMineStrategy,
with new PrecomputedStrategy(). Your code would
theoretically perform identically if all possible decisions were precomputed. In this
case, your code should perform much better than with just ZerosMineStrategy
and MineCountStrategy.
Short
Answer Questions (60%):
Put your
answers to the following in a file called questions.txt (you can use Notepad
for editing). You will be graded on
content, not on spelling or grammar.
1) Put counters (they can be public static void)
into MineWindow and record the total number of calls
to .equals(Object o) and hashCode(). Repeat with your hashCode() changed to return
42.
2) G-T page 413, R-9.4
3) G-T page 413, R-9.6
4) G-T page 413, R-9.8
5) In your own words, why is it so challenging
to make a fast hashCode for a String?
6) Read .equals and hashCode
for List:
http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html
Read .equals and hashCode
for Set:
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Set.html
What is the difference between a Set and a List
that requires the different formulations?
Explain how the requirement of o1.equals(o2) == true Po1.hashCode()==o2.hashCode()
is met.
Explain any attempts to avoid clustering of hashCodes.
Bonus (5%):
Put in
questions.txt too.
If the information in a window deduces to a
rule, then its transpose (reflection around y=x) deduces the same rule. Certainly one way to exploit this fact is to
make sure that every element in the markSet or exploreSet has a matching pair corresponding to it. Another way, if we are concerned about space,
is to have a .equals and a hashCode
that considers both a window and its pair to be equivalent. Put code in here that implements .equals and hashCode for this implementation.
Turn in your work electronically from the “assignments” link on the claswebpage.