墨尔本大学COMP10001课业解析

  • May 15, 2020

题意:编程实现电子投票自动计数功能,对不同的投票方案有良好的支持性解析:背景:大会选举,每位选民只能支持自己最喜欢的候选人,一人一票,获得最多选票的候选人赢得选举。方案一:First Past the Post实现first_past_the_post(votes)函数,参数votes是一个存储选票信息的列表,是一系列代表候选人名字的字符。考虑用遍历列表的方法分别统计每个候选人的频率,比较大小后返回频率最高者的名字;存在最高得票的多个候选人票数一样的情况,返回 “tie”。方案二:Second Preference实现second_preference(votes)函数,参数votes是一个存储选票信息的二重列表。此方案用来解决方案一中,胜出者选票<=50%的情况。首先按第一志愿统计候选人频率,最高得票不过半,删掉第一志愿中得票最低的候选人(有多个按候选人首字母次序删除较前的候选人),并且统计剩余候选人得票数(第一志愿+第二志愿),返回最高者名字,若有多个返回 “tie”。方案三:Multiple Preferences实现multiple_preferences(votes)函数,参数votes是一个存储选票信息的二重列表。方案二只进行一轮,方案三是多轮的改进版。样例中采取5志愿投票,类似方案二的方法进行。涉及知识点:python 列表,二重列表,循环微信号:Ssss_970521pdf全文Project 121 August 2019eVoting• As A/Prof Teague mentioned in her guest lecture – a major challenge is how to run elections online• Imagine you are a programmer for the Australian Electoral Commission, and you have been askedto automate the counting of electronic votes. Can you write programs to automate vote counting fordifferent voting schemes?BackgroundWe consider an election where multiple candidates are running to be the representative of a given electorate.Each voter lodges their vote for their preferred candidate(s).The candidate with the most votes wins the electorate.• Example of a simple voting scheme Candidates: “chris”, “marion”, “nic”Number of votes for each candidate: “chris” : 121, “marion” : 399, “nic” : 180 Winning candidate: “marion” BackgroundA major challenge in voting schemes is how to reflect the preferences of voters, so that the winning candidate has the support of the majority i.e. ideally > 50% of the votes.We will consider three different voting schemes:• First past the post (used in the UK, US, Survivor)
• Second preference
• Multiple preferences (used in Australia)
First Past the Post• This is the simplest voting scheme.• There is a given list of candidates.• Each voter picks their preferred candidate.• We count the number of votes for each candidate.• The candidate with the most votes wins.• Example of a simple voting schemeCandidates: “chris”, “marion”, “nic”
Number of votes for each candidate:
“chris” : 121, “marion” : 399, “nic” : 180
Winning candidate: “marion”
First Past the Post• Example of a simple voting schemeCandidates: “chris”, “marion”, “nic”
Consider an electorate with 9 voters
List of votes:[“chris”, “marion”, “marion”, “nic”, “marion”, “nic”, “nic”, “chris”, “marion”]
Number of votes for each candidate:“chris” : 2, “marion” : 4, “nic” : 3
Winning candidate: “marion”
• Note: winner might not have an absolute majority.i.e., less than 50% of the electorate voted for the winner• Note: an election can result in a tie, where two or more candidates have the highest number of votesCandidates: “chris”, “marion”, “nic”
Consider an electorate with 9 voters
Votes:[“chris”, “nic”, “marion”, “nic”, “chris”, “nic”, “nic”, “chris”, “chris”]
Number of votes for each candidate:“chris” : 4, “marion” : 1, “nic” : 4
Winning candidate: “tie”
Question 1You need to write a function that returns the outcome of an election for a given list of votes using the First Past the Post voting scheme. Note: your function should use either a for loop or a while loop to count the votes.first_past_the_post(votes)votes: list of two or more strings, where each string corresponds to a vote for the candidate whose name is inthe string.Returns a string containing either the name of the candidate with the most votes using First Past the Post voting, or the string “tie” if there is a tie.You can assume that there is no candidate with the name “tie”.Example:v1 = [“chris”, “marion”, “marion”, “nic”, “marion”, “nic”,“nic”, “chris”, “marion”]
first_past_the_post(v1)
returns “marion”

v2 = [“chris”, “nic”, “marion”, “nic”, “chris”, “nic”, “nic”,“chris”, “chris”]
first_past_the_post(v2)
returns “tie”
Second Preference• A drawback of First Past the Post voting is that the winning candidate might not have the majority supportof the voters.• For example, in the first set of votes the majority of voters did not vote for “marion”.• Those voters for the losing candidates “nic” and “chris” might have preferred the other losing candidates ahead of the winner “marion”.• For example, if the voters for “chris” preferred “nic” ahead of “marion”, and the voters for “nic” preferred “chris”ahead of “marion”, then either “chris” or “nic” might be a better consensus winner with the majority of voters.• An alternative voting scheme is to give each voter a second preference.• Each voter gives their first preference candidate and their second preference candidate in their vote, i.e., theypick two candidates in order of decreasing preference.• We then count the votes for each candidate using the first preference votes (in the same way we would for First Past the Post), to see if there is a candidate with an absolute majority of the votes. If there is a candidate with >50% of the first preference votes, then that candidate is the winner.• If there is no candidate with an absolute majority based on the first preference votes, then we look at the secondpreference votes. We find the candidate with the fewest number of first preference votes (the lowest vote candidate). We then look at the second preferences of the votes for that candidate, and reallocate those votes to remaining candidates. The winner is the candidate with the most votes after the reallocation of the second preferences fromlowest vote candidate are added to the first preference votes for the other candidates.• If there are two or more lowest vote candidates with an equal number of first preference votes, reallocate the candidate whose name is lower than the other name if you compare the two names.• Note: a candidate might receive no first preference votes but many second preference votes.Candidates: “chris”, “marion”, “nic”
Consider an electorate with 9 voters
Votes:[[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”], [“nic”, “chris”],[“marion”, “nic”], [“nic”, ”chris”], [“nic”, “chris”], [“chris”, “nic”], [“marion”,“nic”]]
Number of votes for each candidate based on first preferences:“chris” : 2, “marion” : 4, “nic” : 3
No candidate with an absolute majority, “chris” has fewest first preferences.Reallocate second preferences from votes for “chris” to add to first preference votes for other candidates“marion” : 4 + 0, “nic” : 3 + 2
Winning candidate: “nic”

Candidates: “chris”, “marion”, “nic”
Consider an electorate with 6 voters
Votes:[[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”], [“nic”, “chris”],[“chris”, “marion”], [“nic”, ”chris]]
Number of votes for each candidate based on first preferences:“chris” : 2, “marion” : 2, “nic” : 2
No candidate with an absolute majority, all candidates have same number of first preferences.Since “chris” < “marion”< “nic”, reallocate second preferences from votes for “chris” to add to first preference votes for other candidates“marion” : 2 + 1, “nic” : 2 + 1 Winning candidate: “tie” Note:– There is only one round of preference allocation in this scheme – from the candidate with the fewest number of votes.– This method is still not guaranteed to result in a winner with an absolute majority of support.You need to write a function that returns the outcome of an election for a given list of votes using the Second Preference voting scheme.second_preference(votes) votes: list of votes, where each vote is a list that contains two strings,such that the first string is the name of the first preference candidate and the second string is the name of that second preference candidate for that vote.Returns a string containing either the name of the candidate with the most votes using Second Preference voting, or the string “tie” if there is a tie.You can assume that there is no candidate with the name “tie”, and that all votes contain two preferences, and that the two preferences are different, i.e., [“chris”, “chris”] will not appear as a vote in this question.Example:v1 = [[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”],[“nic”, “chris”], [“marion”, “nic”], [“nic”, ”chris”], [“nic”,“chris”], [“chris”, “nic”], [“marion”, “nic”]] second_preference(v1) returns “nic” v2 = [[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”],[“nic”, “chris”], [“chris”, “marion”], [“nic”, ”chris]] second_preference(v2) returns “tie” Example:v3 = [[“chris”, “mini”], [“marion”, “nic”], [“marion”,“chris”], [“nic”, “chris”], [“marion”, “nic”], [“nic”,”chris”], [“nic”, “chris”], [“chris”, “mini”], [“marion”,“nic”]] second_preference(v3) returns “marion” Multiple Preferences• Note that Second Preference voting does not always ensure that the winning candidate has the majority support of the voters (see the third example for Q2).• Our third voting scheme called Multiple Preferences requires each voter to list all candidates in decreasing order of preference.• In this case, we can apply multiple rounds of reallocation,where each time we reallocate the remaining preferences of the candidate with the lowest number of votes so far to the other candidates. We keep doing this until one candidate has an absolute majority, or there are only two candidates left.• As before, if there are two or more lowest vote candidates with an equal number of allocated votes,then reallocate the candidate whose name is lower than the other name if you compare their names.• Note that when reallocating a vote, the next preference may no longer be available if that candidate has already been reallocated, and so we go straight to the following preference (see below).Candidates: “a”, “b”, “c”, “d”, “e” Consider an electorate with 5 voters Votes:[[“a”, “b”, “c”, “d”, “e”], [“b”, “e”, “d”, “c”, “a”], [“c”, “d”, “e”, “b”, “a”],[“d”, “b”, “a”, “c”, “e”], [“e”, “a”, “c”, “b”, “d”]] Number of votes for each candidate based on first preferences:“a” : 1, “b” : 1, “c” : 1, “d” : 1, “e” : 1 No candidate has an absolute majority. Among the equal lowest candidates “a” has the name that is first in sorted orderReallocate vote for “a” to the next preference candidate:“b” [“b”, “e”, “d”, “c”, “a”], [“b”, “c”, “d”, “e”] – from “a”“c” [“c”, “d”, “e”, “b”, “a”]“d” [“d”, “b”, “a”, “c”, “e”]“e” [“e”, “a”, “c”, “b”, “d”]No candidate has an absolute majority. Among the equal lowest candidates(“c”, “d”, “e”), “c” has the name that is first in sorted order.Reallocate vote for “c” to the next preference candidate:“b” [“b”, “e”, “d”, “c”, “a”], [“b”, “c”, “d”, “e”]“d” [“d”, “b”, “a”, “c”, “e”], [“d”, “e”, “b”, “a”] – from “c”“e” [“e”, “a”, “c”, “b”, “d”]No candidate has an absolute majority. “e” is the candidate with the fewestvotes.Reallocate vote for “e” to the next preference candidate (note: both “a” and“c” have already been eliminated, so the next preference from “e” is “b”:“b” [“b”, “e”, “d”, “c”, “a”], [“b”, “c”, “d”, “e”], [“b”, “d”]“d” [“d”, “b”, “a”, “c”, “e”], [“d”, “e”, “b”, “a”]Candidate “b” has an absolute majority and wins the election!Here is another exampleVotes:[[“b”, “c”, “a”], [“c”, “b”, “a”]]Number of votes for each candidate based on first preferences:“a” : 0, “b” : 1, “c” : 1No candidate has an absolute majority. Among the equal lowest candidates“a” has the name that is first in sorted orderAs there are no votes for a, we have no preferences to allocate,and a is eliminated.That leaves two candidates b and c, and we terminate with a tie.*Question 3*You need to write a function that returns the outcome of an election for a given list of votes using the Multiple Preferences voting scheme.multiple_preferences(votes) votes: list of votes, where each vote is a list of strings corresponding to the candidates in decreasing order of preference.Returns a string containing either the name of the candidate with the most votes using Multiple Preferences voting, or the string “tie” if there is a tie.You can assume that there is no candidate with the name “tie”, that each vote contains all candidates, and that each candidate appears only once in each vote.Example:v1 = [[“a”, “b”, “c”, “d”, “e”], [“b”, “e”, “d”, “c”, “a”],[“c”, “d”, “e”, “b”, “a”], [“d”, “b”, “a”, “c”, “e”],[“e”, “a”, “c”, “b”, “d”]] multiple_preferences(v1) returns “b” Example:v2 = [[“a”, “b”, “c”, “d”, “e”], [“b”, “e”, “d”, “c”, “a”],[“c”, “d”, “e”, “b”, “a”], [“d”, “b”, “a”, “c”, “e”],[“d”, “a”, “b”, “c”, “e”], [“e”, “a”, “c”, “b”, “d”]] multiple_preferences(v2) returns “tie” Valid VotesBefore votes are counted in a real election, we need to make sure that a vote is valid, i.e., it does not contain any mistakes.We will focus on checking whether a given vote is valid for Multiple Preferences voting.Consider an electorate with 5 candidates [“a”, “b”, “c”, “d”, “e”][“b”, “e”, “d”, “c”, “a”] is a valid vote[“d”, “b”, “a”, “c”] is not a valid vote in this electorate[“d”, “g”, “b”, “a”, “c”] is not a valid vote in this electorateYou need to write a function that returns True if the given vote is valid for the given list of candidates using the Multiple Preferences voting scheme.is_valid_vote(vote, candidates)vote: a vote to be validated (could have incorrect syntax for a Multiple Preferences vote) candidates: a list of unique strings corresponding to the candidates.Returns a Boolean value True if the given vote is valid for the given list of candidates, or False otherwise.You can assume that the given list of candidates is correctly formattedand does not contain any errors. You should use the specification ofvotes for Multiple Preferences voting as described in Question 3.Example:c = [“tom1”, “li”, “tom2”]is_valid_vote([“tom2, “tom1”, “li”], c)returns Trueis_valid_vote([“tom2”, “tom2”, “li”], c)returns Falseis_valid_vote(“tom2”, c)returns FalseAcademic Honesty• All assessment items (worksheets, projects, test and exam)must be your own, individual, original work.• Any code that is submitted for assessment will beautomatically compared against other students’ code andother code sources using sophisticated similarity checkingsoftware• Cases of potential copying or submitting code that is not yourown may lead to a formal academic misconduct hearing.• Potential penalties can include getting zero for the project,failing the subject, or even expulsion from the university insevere cases.• For further information, please see the university’s AcademicHonesty and Plagiarism website, or ask your lecturer.Academic HonestyThe fastest way to fail the subject is tohand in code that is not your own!!!Academic HonestyFor example:• you must not copy the code of other students• you must not make your code available to others to see• do not give other students your login id and password• do not share USB memory drives• do not post your code on public forums, or any other activitythat would make your code available to others• do not ask other students to see their code• do not submit code that has been written by someone elseIf other students ask to see your code, please say “no”, ascopying (collusion or plagiarism) is considered academicmisconduct, and all students involved may face penalties (boththe student who copied, and the student who made their codeavailable).Conclusion• The project questions will be submitted via Grok.• The project will be made available in Grok shortly aftertoday’s lecture (in a day or so).• You can submit as many times as you like to Grok. We willmark the last version you submit before the deadline. Submitearly and often! Even when your code is incomplete.• We mark your last submission made before the deadline.• The specification of the project questions and the deadlinewill be announced very soon in Grok.• This project is worth 15% of the final subject.• We will be marking the correctness, quality, readability andcommenting of your code.• The deadline (to be confirmed in Grok) will be 23:59 Thursday12 September 2019.

LATEST POSTS
MOST POPULAR

ezAce多年来为广大留学生提供定制写作、留学文书定制、语法润色以及网课代修等服务,超过200位指导老师为您提供24小时不间断地服务。