COMP2009代写编程代做、代写CS，Java程序、c++编程语言调试

日期：2021-05-17 10:33

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.

1. Run with the two different streams of inputs: all random, or all multiples of 10

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

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

2. 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”.

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

2. 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?

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