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.
![](../bluhorsa.gif)
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 220, 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 251 = 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.
![](../bluhorsa.gif)