My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
DesignAndImplementation  
Updated Feb 15, 2012 by tcstewar...@gmail.com

#Design and Implementation of Australian Voting Problem

Problem

The UVa problem presented to us was the Australian Voting Problem. A ballot consists of a list of each candidate in an election, not just a single vote. If there is not a clear winner in a round of voting, all ballots that tied for last will be shifted to the next ranked vote in the ballot. If a candidate loses a round, they are eliminated and can no longer win the election. One of the difficult parts of this problem lies in the fact that the current candidate in the shifted ballot is not guaranteed to not be eliminated, so it is necessary to keep track of which vote is valid on each ballot. Since only eliminated candidates' ballots are reassigned, and you cannot reassign the vote to a previously eliminated candidate, the "index" of which vote to consider can be different on each ballot.

Design

This implementation of the solution to the Australian Voting problem makes use of arrays and vectors to select the winner(s) in rounds of voting. While the bulk of the data structures are global, many of the vectors that store temporary values are native to get_results function. In order to keep from iterating over all the ballots when it is time to shift those ballots that tied for last, a vector of indices to the main ballot array is used to keep track of which indices lost a certain round. There are 3 key functions in the solution, those of which are voting_read, which populates the arrays and other globals to prepare for one round of voting, voting_get_results, which uses the populated globals to return a vector of strings containing the winners, and finally voting_print_results, which prints out the winner(s) to the election.

Algorithm

The bulk of the computation occurs in get_results, which returns the names of the winners to the election. It has no parameters and simply uses the pre-computed globals to carry out the voting process. It works as follows:

  • Iterate through all ballots, using a vector of vector<int>'s to push the candidates onto. For instance, the index of candidate 1 in the ballots array will be pushed onto the vector at position 1. This way we always know how many votes each candidate has along with the indices of losing ballots in the array.
  • Iterate through the eliminated candidates of the previous round, and then shift all ballots with these eliminated candidates over to their next ranked vote, being sure to change the indices vector of vectors accordingly.
  • Loop over candidates and see who has won or lost, returning a winner if it finds a candidate has more than 50% of votes.
  • Iterate through all candidates with the minimum number of vote and eliminate the candidates from the election.

Details

One of the important most important details of this project was insuring that all ballots were not iterated over when shifting ballots with eliminated candidates. For our implementation, we used vectors to aid in this respect, but had we used arrays instead, it could be expected that our solution would perform much faster. However, mere fractions of a second, we believe, could be afforded with the ease of use of vectors over arrays.

Optimizations

Our original algorithm reconsidered every ballot in every round of the election. Since we used arrays instead of vectors it was surprisingly fast, UVa accepted it in .452 seconds. When we changed our algorithm to keep track of which votes needed to be reassigned, it seemed easier to use vectors so we didn't gain a lot of speed. Our optimized version only used .340 seconds. Neither time compares to Professor Downing's .040 seconds, but we were happy with the improvement we achieved.

Challenges

Up until now, we have almost 4 complete working versions of solutions to this problem. The first versions implemented 3 different classes: Round, Candidate, and Ballot. Although our tests show the output to be the same as the current version. We could not get them to pass the UVa online judge. Because of this, we had to start from scratch and devised the much simpler, albeit much harder to read version we have in place now.

Powered by Google Project Hosting