” COMP2009编程 写作、 辅导CSCOMP2009-ACE-ADE 2020-21:Coursework FIVELinear probing and change givingDRAFTWEIGHT: This coursework will contribute 6% of the total module score.DEADLINE: Thursday May 20, 2021, 15:00 (UK time). I will incorporate anychanges (corrections/clarifications) needed, and update.Hence please recheck on Moodle that you have the latest version before sending aquery.DescriptionThe C/W has two parts, brieflyPart I. Understand and use an the implementation of insertion into a simple linear probinghash map to do a simple experimental analysis of the cost of insertion as a function of thefullness, the fill factor, of the hash table. Uses the file HashMap.javaPart II. Finish off the DP Implementation of a change-giving problem. Also, implementthe greedy change-giving method. Report on how often the greedy method gives an optimalanswer in different circumstance. This will need the file change.javaFirstly, you should download the files from Moodle. Your first task should be to read themcarefully, 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 toA. Implement. Understand the code well enough to be able to change the settings forthe 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 studyhow the cost of an insertion (number of probes needed) varies with the number ofentries in the hash table, before the insertion is attempted.1. Run with the two different streams of inputs: all random, or all multiples of 102. Run with the two values N=99 and N=100C. Graph. Using the results of the experiments, plot some graph(s) of the cost c(f) ofan insertions a function of filled, f, the number of entries in the table before theinsertion. 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 tablehelp? Briefly discuss how this would impact of what strategy you would use if youwere designing a Hashmap for a software library.Part II Change givingIn the file ChangeGiving.java you are given partial code for finding the minimum numberof coins to meet a target:You then need toA. Implement DP. Finish off the 2 missing lines in the RunDP implementation ofthe 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 stilloutput values for all values of the target.C. Implement Greedy. Finish off the method RunGreedy(int), to do a greedyselection of coins as given in the lecture repeatedly taking the largest available cointhat 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 Greedymethod compared to the optimal answer obtained from the DP method.1. Consider coinsets based on UK={1,2,5,10,20,50,100,200} andUS={1,5,10,25} and with different multiplicities mult (the number of eachcoin)2. Consider a range of targets, e.g. K = 1,,sumCoins. Note the maximumtarget 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 inwhich the DP reports that it is not possible to give the exact change. E.g. foreach 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 fewestcoins?3. Report on how often the greedy method gives an answer at all, and how oftenit 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 toroughly mimic the case in which you are given some component of a program/methods toanalyse and are required to say something useful about the usefulness and expectedbehaviours.You do not need, and should not attempt, to produce a complete or deep analysis, or write amajor project!! You only need to be able to show that you can run the code, produce someinformative graphs, and make some reasonable interpretation of the effects of changing thesettings such as: hash map size or sets of coins. Hence, demonstrating understanding of thetopics.Submission RequirementsOn 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 SEPARATELYThe 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 Ihad to start again will not be a valid reason for late submission.Marking SchemeThe coursework is worth 6% of the module, and so for clarity will be marked out of 60 so 1mark = 0.1% of module. The division of marks available between the parts is not rigid, but isroughly: Part 1: 30 Part 2: 30When it is required, then attendance and participation in short (less than 5 minutes perperson) individual meeting with tutors. Details will be provided later; but you should expectat 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 studiesand the associated analyses. The quality of analysis of the functions ideally it shouldbe both clear and brief. Does the report demonstrate understanding, and ability to use, the language hashtables 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 PolicyThis coursework must be all your own work. You should remember that the courseworksubmissions 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 theUniversity regulations. If at all in doubt about whether something is allowed, then consult meor your personal tutor.Be aware that may be required to explain your submitted answers to the tutors during alab session.ObjectiveLEARNING OBJECTIVES OF THE C/W: The mildly-open-endedness is a deliberate part ofthe training that this C/W intends to give you. It is vital to develop the skill to decide foryourself what experiments to run, and exactly which graph(s) to produce, rather than justfollowing a precise list produced by someone else. It is generally not possible to decide allexperiments in advance, and so it needs to be done interactively and iteratively – if I specifiedthe experiments then it would basically tell you the answers. This intends to help get start onthe process of learning to design experiments. For example, in doing an individualdissertation in year 3 or 4, you May need to design appropriate tests. If you are in industryand asked to understand the scaling of a complex piece of code then you cannot expect yourboss to provide a list of the experiments to do; but will be expected to figure it out foryourself. Specifically, the objectives of this coursework are to: give some hands-on experience on Hashmaps and how the performance degradeswith them being full and with a bad alignment between the properties of the hashtable and the properties of the input data stream. to be able to understand, implement, simple DP and greedy methods and be able tocompare them, and analyse results from them.Hints and SuggestionsPlease send in email. I may also Collate and maintain a help/FAQ file on Moodle, and/or postthem to the forum.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
