CSC 477/677 Design and Analysis of Algorithms <br> Programming Problem: Electoral College Probabilities

University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

Computer Science 477/677: Design and Analysis of Algorithms

Programming Problem: Containing a Combinatorial Explosion using Dynamic Programming

Revised October 27, 2005.

The Federation of Independent Planets is holding an election for High Chancellor. Each member has a number of electoral votes, as follows.

Earth: 99 electoral votes. (The Federation Constitution prohibits any member from having more than 99 votes. Otherwise, voters on planets other than the Earth might as well not bother to vote.)
The Moon: 12 electoral votes.
Mars: 43 electoral votes.
Ceres: 5 electoral votes.
Juno: 2 electoral votes.
Pallas: 1 electoral vote.
Vesta: 1 electoral vote.
The Astrarchy: 14 electoral votes.
The Hilda Federation: 1 electoral vote.
The East Trojan Union: 12 electoral votes.
The West Trojans: 14 electoral votes.
Io: 2 electoral votes.
Europa: 8 electoral votes.
Ganymede: 5 electoral votes.
Callisto: 1 electoral vote.
Titan: 32 electoral votes.
Umbriel and Uranian Satellites: 4 electoral votes.
Triton: 6 electoral votes.
Pluto-Charon: 1 electoral vote.
Quaoar and the Kuiper Belt: 1 electoral vote.

All the electoral votes of each planet will go to the same candidate. The input gives the number of electors from each planet and the probability that those electors will vote for a certain candidate, expressed as a percentage.
Compute the probability that that certain candidate will win, assuming that the outcomes on the different planets are independent events.
If you simply try all combinations, your program will take exponential time. Since there are 20 "planets," there are 2²⁰, over a million, combinations. You don't need to do that.
Here is another input file showing the United States, and the estimated probability, based on market price at TradeSports on October 24, 2004, that George Bush would win each state.
Now, there are 2⁵¹ = 2,251,799,813,685,248 combinations. If you use the "brute force" method, the election will be over before you finish your computation.
Warning: I don't advise saving this program to place bets on the 2008 Presidential election. In a real election, the outcomes for the different states are not independent, since they are influenced by news stories that are heard in multiple states.