Q6.
a) The number of votes each student received is the number of times their name appears, minus one. This is because each student can cast one vote with their name, so any additional appearances are votes for them.
b) This can be determined by checking the amount of times each person’s name appears. If it only appears once, they didn’t receive any votes, as the one occurrence must be their own vote.
c) There is a total of n votes cast and n students. Therefore, if each student received at least one vote, then the maximum number of votes that can be received by any student is one.
Proof: Every student must receive at least one vote and suppose one student receives two. Since there is a total of n votes, this means there are n-2 votes remaining to distribute between n-1 students. n-2/n-1 < 1, therefore at least one student did not receive any votes, which is a contradiction. Therefore, every student receives at most one vote.
d) Start by representing the students and votes as an undirected graph, with the students as vertices and votes as edges. Use a depth-first search (O(n) time complexity) and note any vertices with only one edge. Since everyone casts a vote, this means the students represented by these vertices didn’t receive any votes, so the vertex they are linked to is the classmate they voted for. Take note of which of these students voted for who. Then, delete the vertices with only one edge from the graph.
The remaining graph should contain cycles between all vertices. Follow each cycle in any direction to collate the remaining votes. (The questions states to produce any list if multiples exist, and it may not be possible to tell precisely who voted for who). The time complexity of this using depth first search is O(V + E) where V is the number of vertices and E is the number of edges. Since V + E <= 2n, this operation also has time complexity O(n).