6. You are conducting an election among a class of n students. Each student cast
ID: 3731726 • Letter: 6
Question
6. You are conducting an election among a class of n students. Each student casts precisely one vote by writing their name, and that of their chosen classmate on a single piece of paper. However, the students have forgotten to specify the order of names on eaclh piece of paper for instance, "Alice Bob" could mean Alice voted for Bob, or Bob voted for Alice (a) [2 marks] Show how you can still uniquely determine how many votes each student received. (b) [1 mark] Hence, explain how you can determine which students did not receive any votes. Can you determine who these students voted for? (c) [2 marks] Suppose every student received at least one vote. What is the maximum possible number of votes received by any student? Justify your answer. (d) [7 + 3 = 10 marks] Using parts (b) and (c), or otherwise, design an algorithm that constructs a list of votes of the form "X voted for Y consistent with the pieces of paper. Specifically, each piece of paper should match up with precisely one of these votes. If multiple such lists exist, produce any. An O(n2) algorithm earns 7 marks, and an O(n) algorithm earns an additional 3 marks. Hint: first, use part (c) to consider how you would solve it in the case where every student received at least one vote. Then, apply part (b).Explanation / Answer
There are no. of votes=no. of students=n;
No. of possible pairs of votes=nC2= n*(n-1).
a)Since every student can cast only a single vote,consider the pair,ALICE-BOB and BOB-ALICE.If the first statement means that Alice voted for Bob then the second statement would definitely mean that Bob voted for Alice.And once Alice appears on the left side of the statement,i.e.,she has already voted,she can only be on the other side of the statement then.So,we can count the number of votes for Alice this way and similarly for other people.
And if this collision doesn't takes place,like if we have three students,A,B and C and we have the following chits:
A-B and B-C.That could mean:
A voted for B.(A can not vote for more now)
B Voted for A(B can't vote any other person).So,that straightway explains the third statement.C voted for B
b)Yes,the students whose names appear only once in all the bits of paper are those who didn't receive any vote.So,with whoever other name they appear is the person they voted for.
c)If every one gets one vote and there is no person that is left,then the maximum no. of votes one can get is 1.Since each student can cast only one vote.
For example,if there are 6 students as A,B,C,D,E and F.And they cast votes as follows(The one on left votes the one on right);then:
A-B;B-C;C-D;D-E;E-F;F-A.As is clear there is maximum one possible vote for everyone
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.