锐客网

  1. 首页 > 睿知 > it技术 > >

COMP2009 线性探求

后端

【COMP2009 线性探求】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.
  3. 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)
  4. 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”.
  5. 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.
  6. 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?
  7. 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

    推荐阅读


    上一篇：UnityEditor|Unity Gizmos使用绘制

    下一篇：非凸科技与东北证券达成战略合作