共计 7054 个字符，预计需要花费 18 分钟才能阅读完成。
COMP2009-ACE-ADE 2020-21:
Coursework FIVE
“Linear probing and change giving”
DRAFT
WEIGHT: This coursework will contribute 6% of the total module score.
DEADLINE: Thursday May 20, 2021, 15:00 (UK time). I will incorporate any
changes (corrections/clarifications) needed, and update.
Hence please recheck on Moodle that you have the latest version before sending a
query.
Description
The C/W has two parts, briefly
Part I. Understand and use an the implementation of insertion into a simple linear probing
hash map to do a simple experimental analysis of the cost of insertion as a function of the
fullness, the“fill factor”, of the hash table. Uses the file HashMap.java
Part II. Finish off the DP implementation of a‘change-giving problem”. Also, implement
the greedy change-giving method. Report on how often the greedy method gives an optimal
answer in different circumstance. This will need the file change.java
Firstly, you should download the files from Moodle. Your first task should be to read them
carefully, and then check that you can edit, compile, and run them as needed.
Part I – Linear probing.
In the file“HashMap.java”you are given partial code for a hash map using linear probing.
You then need to
A.“Implement”. Understand the code well enough to be able to change the settings for
the table size, size of hash table, and properties of the stream of keys inserted.
B.“Experiment”. Run experiments, using various settings within the Java file to study
how the cost of an insertion (number of probes needed) varies with the number of
entries in the hash table, before the insertion is attempted.
- Run with the two different streams of inputs: all random, or all multiples of 10
- Run with the two values N=99 and N=100
C.“Graph”. Using the results of the experiments, plot some graph(s) of the cost c(f) of
an insertions a function of“filled”, f, – the number of entries in the table before the
insertion. E.g. c(0) = 1 as there is never a collision when the table is entry.
D.“Analyse / Report / Strategy selection”. Discuss the results. Are there any surprises.
Is there evidence of whether N=99 or N=100 is better, etc. Does the size of the table
help? Briefly discuss how this would impact of what strategy you would use if you
were designing a“Hashmap”for a software library.
Part II – Change giving
In the file“ChangeGiving.java”you are given partial code for finding the minimum number
of coins to meet a target:
You then need to
A.“Implement DP”. Finish off the 2 missing lines in the“RunDP”implementation of
the change giving using DP. You only need to replace the three placeholder values of
“-99”with actual correct expressions.
B.“Implement DP scan”. In the code the runs a scan of target values, if possible,
improve the code so that it only has to do one invocation of RunDP(), and can still
output values for all values of the target.
C.“Implement Greedy”. Finish off the method RunGreedy(int), to do a greedy
selection of coins as given in the lecture – repeatedly taking the largest available coin
that does not overshoot the target. (Should be just a few lines of code).
D.“Experiments”. Use your code to run experiments to find the success of the Greedy
method compared to the optimal answer obtained from the DP method. - Consider coinsets based on UK={1,2,5,10,20,50,100,200} and
US={1,5,10,25} and with different multiplicities‘mult’(the number of each
coin) - Consider a range of targets, e.g. K = 1,…,sumCoins. Note the maximum
target should never be more than the sum of all the coins.
E.“Analyse and Report”. - Report on circumstances, i.e. combinations of the coinset and target, and in
which the DP reports that it is not possible to give the exact change. E.g. for
each coinset, and the given range of targets, then which fraction of the targets
(assumed no more than the sum of all coins) are achievable. - Report on whether the“UK coinset better or worse than the US coinset”.
E.g. when averaged over some range of values, which coinset needs the fewest
coins? - Report on how often the greedy method gives an answer at all, and how often
it gives an optimal answer.
The reports should be clear and easy to read, and not exceed the page limits.
These questions are deliberately slightly open-ended and under-specified. It is intended to
roughly mimic the case in which you are given some component of a program/methods to
analyse and are required to “say something useful about the usefulness and expected
behaviours”.
You do not need, and should not attempt, to produce a complete or deep analysis, or write a
major project!! You only need to be able to show that you can run the code, produce some
informative graphs, and make some reasonable interpretation of the effects of changing the
settings such as: hash map size or sets of coins. Hence, demonstrating understanding of the
topics.
Submission Requirements
On Moodle, you need to submit a report and your source code (softcopy only).
Specifically, by the deadline, you must submit in Moodle THREE files:
1) The electronic report. This must be a PDF. (Not a .docx file).
2) Your own, (modified as needed), versions of the TWO Java files.
DO NOT ZIP THEM TOGETHER BUT SUBMIT THEM SEPARATELY
The PDF report must be no more than FOUR sides (and do not reduce font size, margins,
etc.) but can/should be significantly less.
As usual, you should be regularly backing up all your work:“My computer crashed, and so I
had to start again”will not be a valid reason for late submission.
Marking Scheme
The coursework is worth 6% of the module, and so for clarity will be marked out of 60 – so 1
mark = 0.1% of module. The division of marks available between the parts is not rigid, but is
roughly:
• Part 1: 30
• Part 2: 30
When it is required, then attendance and participation in short (less than 5 minutes per
person) individual meeting with tutors. Details will be provided later; but you should expect
at least to be able to explain what you did and answer questions about your submission.
Marking Criteria:
The main criteria are:
• The effectiveness and reasonableness of your implementations, experimental studies
and the associated analyses. The quality of analysis of the functions – ideally it should
be both clear and brief.
• Does the report demonstrate understanding, and ability to use, the language hash
tables and of dynamic programming?
Late submissions are allowed and are penalised using the standard University policy: rate
(5% per working day) and with a maximum of 7 days late.
Plagiarism Policy
This coursework must be all your own work. You should remember that the coursework
submissions will be archived, and plagiarism detection tools may be used at any time
(including after the module is finished.) Plagiarism is a very serious offence! Read the
University regulations. If at all in doubt about whether something is allowed, then consult me
or your personal tutor.
Be aware that may be required to explain your submitted answers to the tutors during a
lab session.
Objective
LEARNING OBJECTIVES OF THE C/W: The mildly-open-endedness is a deliberate part of
the training that this C/W intends to give you. It is vital to develop the skill to decide for
yourself what experiments to run, and exactly which graph(s) to produce, rather than just
following a precise list produced by someone else. It is generally not possible to decide all
experiments in advance, and so it needs to be done interactively and iteratively – if I specified
the experiments then it would basically tell you the answers. This intends to help get start on
the process of learning to design experiments. For example, in doing an individual
dissertation in year 3 or 4, you may need to design appropriate tests. If you are in industry
and asked to understand the scaling of a complex piece of code then you cannot expect your
boss to provide a list of the experiments to do; but will be expected to figure it out for
yourself. Specifically, the objectives of this coursework are to:
• give some ‘hands-on’ experience on Hashmaps and how the performance degrades
with them being full and with a bad alignment between the properties of the hash
table and the properties of the input data stream.
• to be able to understand, implement, simple DP and greedy methods and be able to
compare them, and analyse results from them.
Hints and Suggestions
Please send in email. I may also collate and maintain a help/FAQ file on Moodle, and/or post
them to the forum.
Contact: Andrew.Parkes ‘at’ nottingham.ac.uk