Jonathan Bernard

Australian Voting was an interesting project. Like the two projects previous, I had solved this problem before. However, last time I solved it, I did it in Java, and if I remember correctly, I proctrastinated and used a naive algorithm because I ran short on time. This time was quite different. CS371P is using C++, and Prof. Downing has added the following restrictions in the projects so far:

• No dynamic memory allocation (malloc()/free(), new/delete), aka no heap allocations.
• No STL containers

Up until now, these restrictions haven’t really mattered. But this problem was one that would have been much simpler to write using STL containers and dynamic memory. Instead, we are using cstrings, and arrays allocated on the stack for all our data structures. In the end, this probably a good bit faster, but we definitly had some brain-twisting moments. For example, we maintained a list of all the votes currently given to any particular candidate. The datastructure for this is an array  indexed by candidate number of arrays containing indices into the main array of votes representing the votes for each candidate. The length of each of these arrays is equal to the running total of votes for the given candidate. So votes[votesFor[0][0]] represents the first vote that is currently for candidate 0. Of course, the votes array is a two-dimensional array as well, an array of preference arrays and we also need an array to hold the index of the current preference for any given vote. If candidate 0 lost, we need to reassign the vote to the next elegible person in the vote’s preference list. votes[votesFor[0][0]][curPref[0]++] shows us the nest preference for that vote. Add in variables for all the hardcoded values and this can get confusing fast.

• Estimated time to complete: 10 hours.
• Actual time to complete: ~7-8 hours
• Execution time: 0.172
• Rank: 26 28

This entry was posted on Monday, September 28th, 2009 at 8:19 am and is filed under CS371P - OOP, University of Texas. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.